Coverage for /usr/lib/python3/dist-packages/sympy/simplify/combsimp.py: 20%

1from sympy.core import Mul 

2from sympy.core.function import count_ops 

3from sympy.core.traversal import preorder_traversal, bottom_up 

4from sympy.functions.combinatorial.factorials import binomial, factorial 

5from sympy.functions import gamma 

6from sympy.simplify.gammasimp import gammasimp, _gammasimp 

7 

8from sympy.utilities.timeutils import timethis 

9 

10 

11@timethis('combsimp') 

12def combsimp(expr): 

13 r""" 

14 Simplify combinatorial expressions. 

15 

16 Explanation 

17 =========== 

18 

19 This function takes as input an expression containing factorials, 

20 binomials, Pochhammer symbol and other "combinatorial" functions, 

21 and tries to minimize the number of those functions and reduce 

22 the size of their arguments. 

23 

24 The algorithm works by rewriting all combinatorial functions as 

25 gamma functions and applying gammasimp() except simplification 

26 steps that may make an integer argument non-integer. See docstring 

27 of gammasimp for more information. 

28 

29 Then it rewrites expression in terms of factorials and binomials by 

30 rewriting gammas as factorials and converting (a+b)!/a!b! into 

31 binomials. 

32 

33 If expression has gamma functions or combinatorial functions 

34 with non-integer argument, it is automatically passed to gammasimp. 

35 

36 Examples 

37 ======== 

38 

39 >>> from sympy.simplify import combsimp 

40 >>> from sympy import factorial, binomial, symbols 

41 >>> n, k = symbols('n k', integer = True) 

42 

43 >>> combsimp(factorial(n)/factorial(n - 3)) 

44 n*(n - 2)*(n - 1) 

45 >>> combsimp(binomial(n+1, k+1)/binomial(n, k)) 

46 (n + 1)/(k + 1) 

47 

48 """ 

49 

50 expr = expr.rewrite(gamma, piecewise=False) 

51 if any(isinstance(node, gamma) and not node.args[0].is_integer 

52 for node in preorder_traversal(expr)): 

53 return gammasimp(expr); 

54 

55 expr = _gammasimp(expr, as_comb = True) 

56 expr = _gamma_as_comb(expr) 

57 return expr 

58 

59 

60def _gamma_as_comb(expr): 

61 """ 

62 Helper function for combsimp. 

63 

64 Rewrites expression in terms of factorials and binomials 

65 """ 

66 

67 expr = expr.rewrite(factorial) 

68 

69 def f(rv): 

70 if not rv.is_Mul: 

71 return rv 

72 rvd = rv.as_powers_dict() 

73 nd_fact_args = [[], []] # numerator, denominator 

74 

75 for k in rvd: 

76 if isinstance(k, factorial) and rvd[k].is_Integer: 

77 if rvd[k].is_positive: 

78 nd_fact_args[0].extend([k.args[0]]*rvd[k]) 

79 else: 

80 nd_fact_args[1].extend([k.args[0]]*-rvd[k]) 

81 rvd[k] = 0 

82 if not nd_fact_args[0] or not nd_fact_args[1]: 

83 return rv 

84 

85 hit = False 

86 for m in range(2): 

87 i = 0 

88 while i < len(nd_fact_args[m]): 

89 ai = nd_fact_args[m][i] 

90 for j in range(i + 1, len(nd_fact_args[m])): 

91 aj = nd_fact_args[m][j] 

92 

93 sum = ai + aj 

94 if sum in nd_fact_args[1 - m]: 

95 hit = True 

96 

97 nd_fact_args[1 - m].remove(sum) 

98 del nd_fact_args[m][j] 

99 del nd_fact_args[m][i] 

100 

101 rvd[binomial(sum, ai if count_ops(ai) < 

102 count_ops(aj) else aj)] += ( 

103 -1 if m == 0 else 1) 

104 break 

105 else: 

106 i += 1 

107 

108 if hit: 

109 return Mul(*([k**rvd[k] for k in rvd] + [factorial(k) 

110 for k in nd_fact_args[0]]))/Mul(*[factorial(k) 

111 for k in nd_fact_args[1]]) 

112 return rv 

113 

114 return bottom_up(expr, f)