Effective counts and permutations

Question

I have code for counting permutations and combinations, and I try to make it work better for large numbers.

I found a better permutation algorithm that avoids large intermediate results, but I still think I can do better for combinations.

So far I have included a special case to reflect the symmetry of nCr, but I still would like to find a better algorithm that avoids calling factorial (r), which is an unnecessarily large intermediate result. Without this optimization, the last doctrine has been trying for too long to calculate the factor (99,000).

Can someone suggest a more efficient way to count combinations?

from math import factorial def product(iterable): prod = 1 for n in iterable: prod *= n return prod def npr(n, r): """ Calculate the number of ordered permutations of r items taken from a population of size n. >>> npr(3, 2) 6 >>> npr(100, 20) 1303995018204712451095685346159820800000 """ assert 0 <= r <= n return product(range(n - r + 1, n + 1)) def ncr(n, r): """ Calculate the number of unordered combinations of r items taken from a population of size n. >>> ncr(3, 2) 3 >>> ncr(100, 20) 535983370403809682970 >>> ncr(100000, 1000) == ncr(100000, 99000) True """ assert 0 <= r <= n if r > n // 2: r = n - r return npr(n, r) // factorial(r) 

Answer 1

if n is not far from r, then using the recursive definition of the combination is probably better, since xC0 == 1 you will only have a few iterations:

The relevant recursive definition is here:

nCr = (n-1) C (r-1) * n / r

This can be easily calculated using tail recursion with the following list:

(n - r, 1), (n - r + 2, 2), ..., (n - 1, r - 1), (n, r)]

which, of course, is easily generated in Python (we omit the first entry, since nC0 = 1) by izip(xrange(n - r + 1, n+1), xrange(1, r+1)) Note that this assumes r <= n you need to check this and replace them if they are not. Also to optimize use, if r <n / 2, then r = n - r.

Now we just need to apply the recursion step using tail recursion with reduction. We start with 1, since nC0 is 1, and then multiply the current value by the next entry from the list, as shown below.

 from itertools import izip reduce(lambda x, y: x * y[0] / y[1], izip(xrange(n - r + 1, n+1), xrange(1, r+1)), 1) 

Answer 2

Two fairly simple sentences:

• To avoid overflow, do everything in the log space. Use the fact that log (a * b) = log (a) + log (b) and log (a / b) = log (a) - log (b). This simplifies working with very large factorials: log (n! / M!) = Log (n!) - log (m!) Etc.

• Use the gamma function instead of factorial. You can find it at scipy.stats.loggamma . This is a much more efficient way to calculate log factorials than direct summation. loggamma(n) == log(factorial(n - 1)) , and similarly gamma(n) == factorial(n - 1) .

Answer 3

If you don't need a pure-python solution, gmpy2 can help ( gmpy2.comb really fast).

Answer 4

There is a function in scipy for this that has not been mentioned yet: scipy.special.comb . This seems efficient based on some quick time results for your doctest (~ 0.004 seconds for comb(100000, 1000, 1) == comb(100000, 99000, 1) ).

[Although this particular question seems to relate to algorithms, the question is that the math function ncr in python is marked as a duplicate of this ...]

Answer 5

If your problem does not require knowing the exact number of permutations or combinations, you can use the Stirling approximation for factorial.

This will result in the following code:

 import math def stirling(n): # http://en.wikipedia.org/wiki/Stirling%27s_approximation return math.sqrt(2*math.pi*n)*(n/math.e)**n def npr(n,r): return (stirling(n)/stirling(nr) if n>20 else math.factorial(n)/math.factorial(nr)) def ncr(n,r): return (stirling(n)/stirling(r)/stirling(nr) if n>20 else math.factorial(n)/math.factorial(r)/math.factorial(nr)) print(npr(3,2)) # 6 print(npr(100,20)) # 1.30426670868e+39 print(ncr(3,2)) # 3 print(ncr(100,20)) # 5.38333246453e+20 

Answer 6

If you calculate N, choose K (this is what I think you are doing with ncr), there is a dynamic programming solution that can be much faster. This will avoid factorial, plus you can save the table, if you want, for future use.

Here is a tutorial link for it:

http://www.csc.liv.ac.uk/~ped/teachadmin/algor/dyprog.html

I'm not sure how best to solve your first problem though, sorry.

Edit: Here is the layout. There are some pretty funny mistakes that can be at the same time, so it can certainly withstand a little more.

 import sys n = int(sys.argv[1])+2#100 k = int(sys.argv[2])+1#20 table = [[0]*(n+2)]*(n+2) for i in range(1,n): table[i][i] = 1 for i in range(1,n): for j in range(1,ni): x = i+j if j == 1: table[x][j] = 1 else: table[x][j] = table[x-1][j-1] + table[x-1][j] print table[n][k] 

Answer 7

 from scipy import misc misc.comb(n, k) 

should let you count combinations

Answer 8

A more efficient solution for nCr is space wise and accurate.

The mediator (res) is guaranteed to always be int and there will never be more result. The complexity of the space is O (1) (without lists, without fasteners, without a stack), the complexity in time is O (r) - exactly r multiplications and r divisions.

 def ncr(n, r): r = min(r, nr) if r == 0: return 1 res = 1 for k in range(1,r+1): res = res*(n-k+1)/k return res 

Answer 9

Using xrange() instead of range() will speed things up a bit due to the fact that the intermediate list is not created, not populated, not repeated, and not destroyed. Also, reduce() with operator.mul .

Answer 10

For N, select K, you can use the Pascal triangle. Basically, you will need to store an array of size N to calculate all N values ​​of K. Only additions are required.

Answer 11

You can enter two integers and import the math library to find the factorial, and then apply the formula nCr

 import math n,r=[int(_)for _ in raw_input().split()] f=math.factorial print f(n)/f(r)/f(nr) 

Answer 12

 from numpy import prod def nCr(n,r): numerator = range(n, max(nr,r),-1) denominator = range(1, min(nr,r) +1,1) return int(prod(numerator)/prod(denominator))