blocks|key|1010341|text|请参见scipy.special.comb+(旧版本的scipy中的scipy.misc.comb)。当exact为False时，它使用gammaln函数来获得良好的精度，而不需要花费太多时间。在确切的情况下，它返回一个任意精度的整数，这可能需要很长时间来计算。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1010342|entityMap|0|LINK|mutability|MUTABLE|url|https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.comb.html#scipy.special.comb^0|1G|5|3|I|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@$9|O|A|P|B|C]]|D|@$9|Q|A|R|1|S]]|E|$]]|$1|F|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|G|$H|$5|I|J|K|E|$L|M]]]]

See <a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.comb.html#scipy.special.comb" rel="noreferrer">scipy.special.comb</a> (scipy.misc.comb in older versions of scipy). When <code>exact</code> is False, it uses the gammaln function to obtain good precision without taking much time. In the exact case it returns an arbitrary-precision integer, which might take a long time to compute.

blocks|key|1224842|text|在谷歌代码上快速搜索一下(它使用了@Mark+Byers's+answer中的公式)：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1224843|def+choose(n,+k):
++++"""
++++A+fast+way+to+calculate+binomial+coefficients+by+Andrew+Dalke+(contrib).
++++"""
++++if+0+<=+k+<=+n:
++++++++ntok+=+1
++++++++ktok+=+1
++++++++for+t+in+xrange(1,+min(k,+n+-+k)+%2B+1):
++++++++++++ntok+*=+n
++++++++++++ktok+*=+t
++++++++++++n+-=+1
++++++++return+ntok+//+ktok
++++else:
++++++++return+0|code-block|syntax|javascript|1224844|如果你需要一个确切的答案，choose()比scipy.misc.comb()快10倍(在所有0+<=+(n，k)+<+1e3对上进行了测试)。|style|CODE|1224845|def+comb(N,k):+#+from+scipy.comb(),+but+MODIFIED!
++++if+(k+>+N)+or+(N+<+0)+or+(k+<+0):
++++++++return+0L
++++N,k+=+map(long,(N,k))
++++top+=+N
++++val+=+1L
++++while+(top+>+(N-k)):
++++++++val+*=+top
++++++++top+-=+1
++++n+=+1L
++++while+(n+<+k%2B1L):
++++++++val+/=+n
++++++++n+%2B=+1
++++return+val|1224846|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/3025162/statistics-combinations-in-python/3025194#3025194^0|H|K|0|0|0|D|8|M|H|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@$A|X|B|Y|1|Z]]|C|$]]|$1|D|3|E|5|F|7|10|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|11|8|@$A|12|B|13|K|L]|$A|14|B|15|K|L]]|9|@]|C|$]]|$1|M|3|N|5|F|7|16|8|@]|9|@]|C|$G|H]]|$1|O|3|-4|5|6|7|17|8|@]|9|@]|C|$]]]|P|$Q|$5|R|S|T|C|$U|V]]]]

A quick search on google code gives (it uses formula from <a href="https://stackoverflow.com/questions/3025162/statistics-combinations-in-python/3025194#3025194">@Mark Byers's answer</a>):

<pre><code>def choose(n, k):
 """
 A fast way to calculate binomial coefficients by Andrew Dalke (contrib).
 """
 if 0 &lt;= k &lt;= n:
 ntok = 1
 ktok = 1
 for t in xrange(1, min(k, n - k) + 1):
 ntok *= n
 ktok *= t
 n -= 1
 return ntok // ktok
 else:
 return 0
</code></pre>

<code>choose()</code> is 10 times faster (tested on all 0 &lt;= (n,k) &lt; 1e3 pairs) than <code>scipy.misc.comb()</code> if you need an exact answer.

<pre><code>def comb(N,k): # from scipy.comb(), but MODIFIED!
 if (k &gt; N) or (N &lt; 0) or (k &lt; 0):
 return 0L
 N,k = map(long,(N,k))
 top = N
 val = 1L
 while (top &gt; (N-k)):
 val *= top
 top -= 1
 n = 1L
 while (n &lt; k+1L):
 val /= n
 n += 1
 return val
</code></pre>

blocks|key|1224873|text|为什么不自己写呢？这是一行或类似的：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1224874|from+operator+import+mul++++#+or+mul=lambda+x,y:x*y
from+fractions+import+Fraction

def+nCk(n,k):+
++return+int(+reduce(mul,+(Fraction(n-i,+i%2B1)+for+i+in+range(k)),+1)+)|code-block|syntax|javascript|1224875|测试打印帕斯卡三角形：|1224876|>>>+for+n+in+range(17):
...+++++print+'+'.join('%255d'%25nCk(n,k)+for+k+in+range(n%2B1)).center(100)
...+++++
+++++++++++++++++++++++++++++++++++++++++++++++++++1++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++1+++++1+++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++1+++++2+++++1++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++1+++++3+++++3+++++1+++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++1+++++4+++++6+++++4+++++1++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++1+++++5++++10++++10+++++5+++++1+++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++1+++++6++++15++++20++++15+++++6+++++1++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++1+++++7++++21++++35++++35++++21+++++7+++++1+++++++++++++++++++++++++++
+++++++++++++++++++++++++++1+++++8++++28++++56++++70++++56++++28+++++8+++++1++++++++++++++++++++++++
++++++++++++++++++++++++1+++++9++++36++++84+++126+++126++++84++++36+++++9+++++1+++++++++++++++++++++
+++++++++++++++++++++1++++10++++45+++120+++210+++252+++210+++120++++45++++10+++++1++++++++++++++++++
++++++++++++++++++1++++11++++55+++165+++330+++462+++462+++330+++165++++55++++11+++++1+++++++++++++++
+++++++++++++++1++++12++++66+++220+++495+++792+++924+++792+++495+++220++++66++++12+++++1++++++++++++
++++++++++++1++++13++++78+++286+++715++1287++1716++1716++1287+++715+++286++++78++++13+++++1+++++++++
+++++++++1++++14++++91+++364++1001++2002++3003++3432++3003++2002++1001+++364++++91++++14+++++1++++++
++++++1++++15+++105+++455++1365++3003++5005++6435++6435++5005++3003++1365+++455+++105++++15+++++1+++
++++1++++16+++120+++560++1820++4368++8008+11440+12870+11440++8008++4368++1820+++560+++120++++16+++++1
>>>+|1224877|PS。经过编辑，将int(round(reduce(mul,+(float(n-i)/(i%2B1)+for+i+in+range(k)),+1)))替换为int(reduce(mul,+(Fraction(n-i,+i%2B1)+for+i+in+range(k)),+1))，因此它不会在大N/K时出错|offset|length|style|CODE|1224878|entityMap^0|0|0|0|0|9|1S|24|1N|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|W|8|@$M|X|N|Y|O|P]|$M|Z|N|10|O|P]]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|11|8|@]|9|@]|A|$]]]|R|$]]

Why not write it yourself? It's a one-liner or such:

<pre><code>from operator import mul # or mul=lambda x,y:x*y
from fractions import Fraction

def nCk(n,k): 
 return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )
</code></pre>

Test - printing Pascal's triangle:

<pre><code>&gt;&gt;&gt; for n in range(17):
... print ' '.join('%5d'%nCk(n,k) for k in range(n+1)).center(100)
... 
 1 
 1 1 
 1 2 1 
 1 3 3 1 
 1 4 6 4 1 
 1 5 10 10 5 1 
 1 6 15 20 15 6 1 
 1 7 21 35 35 21 7 1 
 1 8 28 56 70 56 28 8 1 
 1 9 36 84 126 126 84 36 9 1 
 1 10 45 120 210 252 210 120 45 10 1 
 1 11 55 165 330 462 462 330 165 55 11 1 
 1 12 66 220 495 792 924 792 495 220 66 12 1 
 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 
 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 
 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 
 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
&gt;&gt;&gt; 
</code></pre>

PS. edited to replace <code>int(round(reduce(mul, (float(n-i)/(i+1) for i in range(k)), 1)))</code>
with <code>int(reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1))</code> so it won't err for big N/K

blocks|key|1010452|text|这是另一种选择。这个函数最初是用C%2B%2B编写的，因此它可以向后移植到C%2B%2B，以获得一个有限精度的整数(例如__int64)。优点是(1)它只涉及整数运算，(2)它通过执行连续的乘法和除法对来避免整数值膨胀。我已经用Nas+Banov的Pascal三角形测试了结果，它得到了正确的答案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1010453|def+choose(n,r):
++"""Computes+n!+/+(r!+(n-r)!)+exactly.+Returns+a+python+long+int."""
++assert+n+>=+0
++assert+0+<=+r+<=+n

++c+=+1L
++denom+=+1
++for+(num,denom)+in+zip(xrange(n,n-r,-1),+xrange(1,r%2B1,1)):
++++c+=+(c+*+num)+//+denom
++return+c|code-block|syntax|javascript|1010454|基本原理:为了最小化乘法和除法的数量，我们将表达式重写为|1010455|++++n!++++++n(n-1)...(n-r%2B1)
---------+=+----------------
+r!(n-r)!++++++++++r!|1010456|为了尽可能避免乘法溢出，我们将严格按照从左到右的顺序进行求值：|1010457|n+/+1+*+(n-1)+/+2+*+(n-2)+/+3+*+...+*+(n-r%2B1)+/+r|1010458|我们可以证明以这种顺序运算的整数是精确的(即没有舍入误差)。|1010459|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|W|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|X|8|@]|9|@]|A|$E|F]]|$1|O|3|P|5|6|7|Y|8|@]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|R|$]]

Here's another alternative. This one was originally written in C++, so it can be backported to C++ for a finite-precision integer (e.g. __int64). The advantage is (1) it involves only integer operations, and (2) it avoids bloating the integer value by doing successive pairs of multiplication and division. I've tested the result with Nas Banov's Pascal triangle, it gets the correct answer:

<pre><code>def choose(n,r):
 """Computes n! / (r! (n-r)!) exactly. Returns a python long int."""
 assert n &gt;= 0
 assert 0 &lt;= r &lt;= n

 c = 1L
 denom = 1
 for (num,denom) in zip(xrange(n,n-r,-1), xrange(1,r+1,1)):
 c = (c * num) // denom
 return c
</code></pre>

Rationale: To minimize the # of multiplications and divisions, we rewrite the expression as

<pre><code> n! n(n-1)...(n-r+1)
--------- = ----------------
 r!(n-r)! r!
</code></pre>

To avoid multiplication overflow as much as possible, we will evaluate in the following STRICT order, from left to right:

<pre><code>n / 1 * (n-1) / 2 * (n-2) / 3 * ... * (n-r+1) / r
</code></pre>

We can show that integer arithmatic operated in this order is exact (i.e. no roundoff error).

blocks|key|1010503|text|数学定义的直译在很多情况下就足够了(请记住，Python将自动使用大数算法)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1010504|from+math+import+factorial

def+calculate_combinations(n,+r):
++++return+factorial(n)+//+factorial(r)+//+factorial(n-r)|code-block|syntax|javascript|1010505|对于我测试的一些输入(例如n=1000+r=500)，这比liner+reduce在另一个(目前投票最高的)答案中建议的速度快10倍以上。另一方面，它的性能被@J.F.Sebastian提供的snippit所超越。|offset|length|style|CODE|1010506|entityMap^0|0|0|Z|6|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@$I|R|J|S|K|L]]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

A literal translation of the mathematical definition is quite adequate in a lot of cases (remembering that Python will automatically use big number arithmetic):

<pre><code>from math import factorial

def calculate_combinations(n, r):
 return factorial(n) // factorial(r) // factorial(n-r)
</code></pre>

For some inputs I tested (e.g. n=1000 r=500) this was more than 10 times faster than the one liner <code>reduce</code> suggested in another (currently highest voted) answer. On the other hand, it is out-performed by the snippit provided by @J.F. Sebastian.

blocks|key|1010552|text|如果您希望得到准确的结果，请使用sympy.binomial。毫无疑问，这似乎是最快的方法。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1010553|x+=+1000000
y+=+234050

%25timeit+scipy.misc.comb(x,+y,+exact=True)
1+loops,+best+of+3:+1min+27s+per+loop

%25timeit+gmpy.comb(x,+y)
1+loops,+best+of+3:+1.97+s+per+loop

%25timeit+int(sympy.binomial(x,+y))
100000+loops,+best+of+3:+5.06+µs+per+loop|code-block|syntax|javascript|1010554|entityMap|0|LINK|mutability|MUTABLE|url|http://docs.sympy.org/0.6.7/modules/functions.html#binomial^0|G|E|G|E|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@$9|T|A|U|B|C]]|D|@$9|V|A|W|1|X]]|E|$]]|$1|F|3|G|5|H|7|Y|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|Z|8|@]|D|@]|E|$]]]|L|$M|$5|N|O|P|E|$Q|R]]]]

If you want an exact result, use <a href="http://docs.sympy.org/0.6.7/modules/functions.html#binomial"><code>sympy.binomial</code></a>. It seems to be the fastest method, hands down.

<pre><code>x = 1000000
y = 234050

%timeit scipy.misc.comb(x, y, exact=True)
1 loops, best of 3: 1min 27s per loop

%timeit gmpy.comb(x, y)
1 loops, best of 3: 1.97 s per loop

%timeit int(sympy.binomial(x, y))
100000 loops, best of 3: 5.06 µs per loop
</code></pre>

blocks|key|1010583|text|使用动态编程，时间复杂度为Θ(n*m)，空间复杂度为Θ(m)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1010584|def+binomial(n,+k):
"""+(int,+int)+->+int

+++++++++%7C+c(n-1,+k-1)+%2B+c(n-1,+k),+if+0+<+k+<+n
c(n,k)+=+%7C+1++++++++++++++++++++++,+if+n+=+k
+++++++++%7C+1++++++++++++++++++++++,+if+k+=+0

Precondition:+n+>+k

>>>+binomial(9,+2)
36
"""

c+=+[0]+*+(n+%2B+1)
c[0]+=+1
for+i+in+range(1,+n+%2B+1):
++++c[i]+=+1
++++j+=+i+-+1
++++while+j+>+0:
++++++++c[j]+%2B=+c[j+-+1]
++++++++j+-=+1

return+c[k]|code-block|syntax|javascript|1010585|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Using dynamic programming, the time complexity is Θ(n*m) and space complexity Θ(m):

<pre><code>def binomial(n, k):
""" (int, int) -&gt; int

 | c(n-1, k-1) + c(n-1, k), if 0 &lt; k &lt; n
c(n,k) = | 1 , if n = k
 | 1 , if k = 0

Precondition: n &gt; k

&gt;&gt;&gt; binomial(9, 2)
36
"""

c = [0] * (n + 1)
c[0] = 1
for i in range(1, n + 1):
 c[i] = 1
 j = i - 1
 while j &gt; 0:
 c[j] += c[j - 1]
 j -= 1

return c[k]
</code></pre>

blocks|key|1010665|text|对于相当大的输入，这可能是您在纯python中所能做到的最快速度：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1010666|def+choose(n,+k):
++++if+k+==+n:+return+1
++++if+k+>+n:+return+0
++++d,+q+=+max(k,+n-k),+min(k,+n-k)
++++num+=++1
++++for+n+in+xrange(d%2B1,+n%2B1):+num+*=+n
++++denom+=+1
++++for+d+in+xrange(1,+q%2B1):+denom+*=+d
++++return+num+/+denom|code-block|syntax|javascript|1010667|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

That's probably as fast as you can do it in pure python for reasonably large inputs:

<pre><code>def choose(n, k):
 if k == n: return 1
 if k &gt; n: return 0
 d, q = max(k, n-k), min(k, n-k)
 num = 1
 for n in xrange(d+1, n+1): num *= n
 denom = 1
 for d in xrange(1, q+1): denom *= d
 return num / denom
</code></pre>

blocks|key|1010731|text|当n大于20时，直接公式产生大整数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1010732|因此，还有另一种回应：|1010733|from+math+import+factorial

reduce(long.__mul__,+range(n-r%2B1,+n%2B1),+1L)+//+factorial(r)|code-block|syntax|javascript|1010734|简短、准确和高效，因为这避免了python使用长整型。|1010735|与scipy.special.comb相比，它更准确、更快：|1010736|+>>>+from+scipy.special+import+comb
+>>>+nCr+=+lambda+n,r:+reduce(long.__mul__,+range(n-r%2B1,+n%2B1),+1L)+//+factorial(r)
+>>>+comb(128,20)
+1.1965669823265365e%2B23
+>>>+nCr(128,20)
+119656698232656998274400L++#+accurate,+no+loss
+>>>+from+timeit+import+timeit
+>>>+timeit(lambda:+comb(n,r))
+8.231969118118286
+>>>+timeit(lambda:+nCr(128,+20))
+3.885951042175293|1010737|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|S|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|T|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|N|5|F|7|V|8|@]|9|@]|A|$G|H]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

The direct formula produces big integers when n is bigger than 20. 

So, yet another response:

<pre><code>from math import factorial

reduce(long.__mul__, range(n-r+1, n+1), 1L) // factorial(r)
</code></pre>

short, accurate and efficient because this avoids python big integers by sticking with longs. 

It is more accurate and faster when comparing to scipy.special.comb:

<pre><code> &gt;&gt;&gt; from scipy.special import comb
 &gt;&gt;&gt; nCr = lambda n,r: reduce(long.__mul__, range(n-r+1, n+1), 1L) // factorial(r)
 &gt;&gt;&gt; comb(128,20)
 1.1965669823265365e+23
 &gt;&gt;&gt; nCr(128,20)
 119656698232656998274400L # accurate, no loss
 &gt;&gt;&gt; from timeit import timeit
 &gt;&gt;&gt; timeit(lambda: comb(n,r))
 8.231969118118286
 &gt;&gt;&gt; timeit(lambda: nCr(128, 20))
 3.885951042175293
</code></pre>

blocks|key|1225260|text|使用sympy很容易。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1225261|import+sympy

comb+=+sympy.binomial(n,+r)|code-block|syntax|javascript|1225262|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

It's pretty easy with sympy.

<pre><code>import sympy

comb = sympy.binomial(n, r)
</code></pre>

blocks|key|1225322|text|如果您的程序有n的上限(比如n+<=+N)，并且需要重复计算nCr+(最好是>>N时间)，那么使用lru_cache可以给您带来巨大的性能提升：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1225323|from+functools+import+lru_cache

@lru_cache(maxsize=None)
def+nCr(n,+r):
++++return+1+if+r+==+0+or+r+==+n+else+nCr(n+-+1,+r+-+1)+%2B+nCr(n+-+1,+r)|code-block|syntax|javascript|1225324|构造缓存(这是隐式完成的)最多占用O(N%5E2)时间。任何后续对nCr的调用都将在O(1)中返回。|1225325|entityMap|0|LINK|mutability|MUTABLE|url|http://book.pythontips.com/en/latest/function_caching.html^0|7|1|E|6|14|1|1D|9|0|0|0|H|6|V|3|14|4|0^^$0|@$1|2|3|4|5|6|7|U|8|@$9|V|A|W|B|C]|$9|X|A|Y|B|C]|$9|Z|A|10|B|C]]|D|@$9|11|A|12|1|13]]|E|$]]|$1|F|3|G|5|H|7|14|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|15|8|@$9|16|A|17|B|C]|$9|18|A|19|B|C]|$9|1A|A|1B|B|C]]|D|@]|E|$]]|$1|M|3|-4|5|6|7|1C|8|@]|D|@]|E|$]]]|N|$O|$5|P|Q|R|E|$S|T]]]]

If your program has an upper bound to <code>n</code> (say <code>n &lt;= N</code>) and needs to repeatedly compute nCr (preferably for >><code>N</code> times), using <a href="http://book.pythontips.com/en/latest/function_caching.html" rel="noreferrer">lru_cache</a> can give you a huge performance boost:

<pre><code>from functools import lru_cache

@lru_cache(maxsize=None)
def nCr(n, r):
 return 1 if r == 0 or r == n else nCr(n - 1, r - 1) + nCr(n - 1, r)
</code></pre>

Constructing the cache (which is done implicitly) takes up to <code>O(N^2)</code> time. Any subsequent calls to <code>nCr</code> will return in <code>O(1)</code>.

blocks|key|1010887|text|你可以写两个简单的函数，实际上比使用scipy.special.comb快5-8倍。实际上，您不需要导入任何额外的包，并且该函数非常容易阅读。诀窍是使用memoization来存储先前计算的值，并使用nCr的定义|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1010888|#+create+a+memoization+dictionary
memo+=+{}
def+factorial(n):
++++"""
++++Calculate+the+factorial+of+an+input+using+memoization
++++:param+n:+int
++++:rtype+value:+int
++++"""
++++if+n+in+[1,0]:
++++++++return+1
++++if+n+in+memo:
++++++++return+memo[n]
++++value+=+n*factorial(n-1)
++++memo[n]+=+value
++++return+value

def+ncr(n,+k):
++++"""
++++Choose+k+elements+from+a+set+of+n+elements+-+n+must+be+larger+than+or+equal+to+k
++++:param+n:+int
++++:param+k:+int
++++:rtype:+int
++++"""
++++return+factorial(n)/(factorial(k)*factorial(n-k))|code-block|syntax|javascript|1010889|如果我们比较时间|1010890|from+scipy.special+import+comb
%25timeit+comb(100,48)
>>>+100000+loops,+best+of+3:+6.78+µs+per+loop

%25timeit+ncr(100,48)
>>>+1000000+loops,+best+of+3:+1.39+µs+per+loop|1010891|entityMap|0|LINK|mutability|MUTABLE|url|https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.comb.html#scipy.special.comb|1|https://en.wikipedia.org/wiki/Binomial_coefficient^0|I|I|0|2S|3|1|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@$A|X|B|Y|1|Z]|$A|10|B|11|1|12]]|C|$]]|$1|D|3|E|5|F|7|13|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|14|8|@]|9|@]|C|$]]|$1|K|3|L|5|F|7|15|8|@]|9|@]|C|$G|H]]|$1|M|3|-4|5|6|7|16|8|@]|9|@]|C|$]]]|N|$O|$5|P|Q|R|C|$S|T]]|U|$5|P|Q|R|C|$S|V]]]]

You can write 2 simple functions that actually turns out to be about 5-8 times faster than using <a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.comb.html#scipy.special.comb" rel="nofollow noreferrer">scipy.special.comb</a>. In fact, you don't need to import any extra packages, and the function is quite easily readable. The trick is to use memoization to store previously computed values, and using the definition of <a href="https://en.wikipedia.org/wiki/Binomial_coefficient" rel="nofollow noreferrer">nCr</a>

<pre><code># create a memoization dictionary
memo = {}
def factorial(n):
 """
 Calculate the factorial of an input using memoization
 :param n: int
 :rtype value: int
 """
 if n in [1,0]:
 return 1
 if n in memo:
 return memo[n]
 value = n*factorial(n-1)
 memo[n] = value
 return value

def ncr(n, k):
 """
 Choose k elements from a set of n elements - n must be larger than or equal to k
 :param n: int
 :param k: int
 :rtype: int
 """
 return factorial(n)/(factorial(k)*factorial(n-k))
</code></pre>

If we compare times

<pre><code>from scipy.special import comb
%timeit comb(100,48)
&gt;&gt;&gt; 100000 loops, best of 3: 6.78 µs per loop

%timeit ncr(100,48)
&gt;&gt;&gt; 1000000 loops, best of 3: 1.39 µs per loop
</code></pre>

blocks|key|1010916|text|这是使用内置memoization装饰器的@+using+erT2333代码。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1010917|from+functools+import+lru_cache

@lru_cache()
def+factorial(n):
++++"""
++++Calculate+the+factorial+of+an+input+using+memoization
++++:param+n:+int
++++:rtype+value:+int
++++"""
++++return+1+if+n+in+(1,+0)+else+n+*+factorial(n-1)

@lru_cache()
def+ncr(n,+k):
++++"""
++++Choose+k+elements+from+a+set+of+n+elements,
++++n+must+be+greater+than+or+equal+to+k.
++++:param+n:+int
++++:param+k:+int
++++:rtype:+int
++++"""
++++return+factorial(n)+/+(factorial(k)+*+factorial(n+-+k))

print(ncr(6,+3))|code-block|syntax|javascript|1010918|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

This is @killerT2333 code using the builtin memoization decorator.

<pre><code>from functools import lru_cache

@lru_cache()
def factorial(n):
 """
 Calculate the factorial of an input using memoization
 :param n: int
 :rtype value: int
 """
 return 1 if n in (1, 0) else n * factorial(n-1)

@lru_cache()
def ncr(n, k):
 """
 Choose k elements from a set of n elements,
 n must be greater than or equal to k.
 :param n: int
 :param k: int
 :rtype: int
 """
 return factorial(n) / (factorial(k) * factorial(n - k))

print(ncr(6, 3))
</code></pre>

blocks|key|1225397|text|这个函数是非常优化的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1225398|def+nCk(n,k):
++++m=0
++++if+k==0:
++++++++m=1
++++if+k==1:
++++++++m=n
++++if+k>=2:
++++++++num,dem,op1,op2=1,1,k,n
++++++++while(op1>=1):
++++++++++++num*=op2
++++++++++++dem*=op1
++++++++++++op1-=1
++++++++++++op2-=1
++++++++m=num//dem
++++return+m|code-block|syntax|javascript|1225399|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

This function is very optimized.
<pre><code>def nCk(n,k):
 m=0
 if k==0:
 m=1
 if k==1:
 m=n
 if k&gt;=2:
 num,dem,op1,op2=1,1,k,n
 while(op1&gt;=1):
 num*=op2
 dem*=op1
 op1-=1
 op2-=1
 m=num//dem
 return m
</code></pre>

blocks|key|1010999|text|这是一个非常有效的算法|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1011000|for+i+=+1.....r

+++p+=+p+*+(+n+-+i+)+/+i

print(p)|code-block|syntax|javascript|1011001|例如nCr(+30+,7)+=+fact(30)+/(+fact(7)+*+fact(23))+=(30*+29+*+28+*+27+*+26+*+25+*+24+)/+(1+*2*3*4*5*6*+7)|1011002|所以只要运行从1到r的循环就可以得到结果。|1011003|1011004|在python中：|1011005|n,r=5,2
p=n
for+i+in+range(1,r):
+++p+=+p*(n+-+i)/i
else:
+++p+=+p/(i%2B1)
print(p)|1011006|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|S|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|T|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|U|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|V|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|W|8|@]|9|@]|A|$]]|$1|N|3|O|5|D|7|X|8|@]|9|@]|A|$E|F]]|$1|P|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]]|Q|$]]

Here is an efficient algorithm for you
<pre><code>for i = 1.....r

 p = p * ( n - i ) / i

print(p)
</code></pre>
For example nCr(30,7)
= fact(30) / ( fact(7) * fact(23))
= ( 30 * 29 * 28 * 27 * 26 * 25 * 24 ) / (1 * 2 * 3 * 4 * 5 * 6 * 7)
So just run the loop from 1 to r can get the result.
<hr />
In python:
<pre class="lang-py prettyprint-override"><code>n,r=5,2
p=n
for i in range(1,r):
 p = p*(n - i)/i
else:
 p = p/(i+1)
print(p)
</code></pre>

blocks|key|1225586|text|我从这个线程和这里链接的库中计时了17个不同的函数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1225587|Since+I+feel+it's+a+bit+much+to+dump+here,+I+put+the+code+for+the+functions+in+a+pastebin+here.|offset|length|1225588|我做的第一个测试是构建到第100行的pascal三角形。我用timeit做了100次这样的事情。下面的数字是构建一次三角形所需的平均时间(秒)。|1225589|gmpy2.gmpy2.comb+0.0012259269999998423
math.comb+0.007063110999999935
__main__.stdfactorial2+0.011469491
__main__.scipybinom+0.0120114319999999
__main__.stdfactorial+0.012105122
__main__.scipycombexact+0.012569045999999844
__main__.andrewdalke+0.01825201100000015
__main__.rabih+0.018472497000000202
__main__.kta+0.019374668000000383
__main__.wirawan+0.029312811000000067
scipy.special._basic.comb+0.03221609299999954
__main__.jfsmodifiedscipy+0.04332894699999997
__main__.rojas+0.04395155400000021
sympy.functions.combinatorial.factorials.binomial+0.3233529779999998
__main__.nasbanov+0.593365528
__main__.pantelis300+1.7780402499999999|code-block|syntax|javascript|1225590|你可能注意到这里只有16个函数。这是因为recursive()函数甚至不能在合理的时间内完成一次，所以我必须将其排除在timeit测试之外。说真的，已经持续了好几个小时了。|style|CODE|1225591|我还对不是所有上述函数都支持的其他类型的输入进行了计时。请记住，我每10次只运行一次测试，因为nCr的计算成本很高，而且我没有耐心|1225592|N的小数值|1225593|__main__.scipybinom+0.011481370000000001
__main__.kta+0.01869513999999999
sympy.functions.combinatorial.factorials.binomial+6.33897291|1225594|R的小数值|1225595|__main__.scipybinom+0.010960040000000504
scipy.special._basic.comb+0.03681254999999908
sympy.functions.combinatorial.factorials.binomial+3.2962564499999987|1225596|N和r的小数值|1225597|__main__.scipybinom+0.008623409999998444
sympy.functions.combinatorial.factorials.binomial+3.690936439999999|1225598|N的负值|1225599|gmpy2.gmpy2.comb+0.010770989999997482
__main__.kta+0.02187850000000253
__main__.rojas+0.05104292999999984
__main__.nasbanov+0.6153183200000001
sympy.functions.combinatorial.factorials.binomial+3.0460310799999943|1225600|n的负分数值，r的分数值|1225601|sympy.functions.combinatorial.factorials.binomial+3.7689941699999965|1225602|目前实现最大速度和多功能性的最佳解决方案是一个混合函数，可以根据输入在不同的算法之间进行选择|1225603|def+hybrid(n:+typing.Union[int,+float],+k:+typing.Union[int,+float])+->+typing.Union[int,+float]:
++++#+my+own+custom+hybrid+solution
++++def+is_integer(n):
++++++++return+isinstance(n,+int)+or+n.is_integer()
++++if+k+<+0:
++++++++raise+ValueError("k+cannot+be+negative.")
++++elif+n+==+0:
++++++++return+0
++++elif+k+==+0+or+k+==+n:
++++++++return+1
++++elif+is_integer(n)+and+is_integer(k):
++++++++return+int(gmpy2.comb(int(n),+int(k)))
++++elif+n+>+0:
++++++++return+scipy.special.binom(n,+k)
++++else:
++++++++return+float(sympy.binomial(n,+k))|1225604|由于sympy.binomial()非常慢，真正理想的解决方案应该是将scipy.special.binom()的代码和gmpy2.comb()的代码结合起来，前者对于小数的性能很好，而后者对于整数的性能很好。scipy's+func和gympy2's+func都是用我不太熟悉的C语言编写的。|1225605|entityMap|0|LINK|mutability|MUTABLE|url|https://pastebin.com/jSNN6sNf|1|https://github.com/scipy/scipy/blob/701ffcc8a6f04509d115aac5e5681c538b5265a2/scipy/special/orthogonal_eval.pxd#L67-L126|2|https://github.com/aleaxit/gmpy/blob/00ba694027e72aa629260032c3103feadff54c09/src/gmpy2_mpz_misc.c#L775-L828^0|0|0|2N|0|0|0|0|K|B|0|0|0|0|0|0|0|0|0|0|0|0|0|0|2|G|Z|L|1O|C|2X|C|1|3A|D|2|0^^$0|@$1|2|3|4|5|6|7|1U|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1V|8|@]|9|@$D|1W|E|1X|1|1Y]]|A|$]]|$1|F|3|G|5|6|7|1Z|8|@]|9|@]|A|$]]|$1|H|3|I|5|J|7|20|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|21|8|@$D|22|E|23|O|P]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|24|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|25|8|@]|9|@]|A|$]]|$1|U|3|V|5|J|7|26|8|@]|9|@]|A|$K|L]]|$1|W|3|X|5|6|7|27|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|J|7|28|8|@]|9|@]|A|$K|L]]|$1|10|3|11|5|6|7|29|8|@]|9|@]|A|$]]|$1|12|3|13|5|J|7|2A|8|@]|9|@]|A|$K|L]]|$1|14|3|15|5|6|7|2B|8|@]|9|@]|A|$]]|$1|16|3|17|5|J|7|2C|8|@]|9|@]|A|$K|L]]|$1|18|3|19|5|6|7|2D|8|@]|9|@]|A|$]]|$1|1A|3|1B|5|J|7|2E|8|@]|9|@]|A|$K|L]]|$1|1C|3|1D|5|6|7|2F|8|@]|9|@]|A|$]]|$1|1E|3|1F|5|J|7|2G|8|@]|9|@]|A|$K|L]]|$1|1G|3|1H|5|6|7|2H|8|@$D|2I|E|2J|O|P]|$D|2K|E|2L|O|P]|$D|2M|E|2N|O|P]]|9|@$D|2O|E|2P|1|2Q]|$D|2R|E|2S|1|2T]]|A|$]]|$1|1I|3|-4|5|6|7|2U|8|@]|9|@]|A|$]]]|1J|$1K|$5|1L|1M|1N|A|$1O|1P]]|1Q|$5|1L|1M|1N|A|$1O|1R]]|1S|$5|1L|1M|1N|A|$1O|1T]]]]

I timed 17 different functions from this thread and libraries linked here.
<a href="https://pastebin.com/jSNN6sNf" rel="nofollow noreferrer">Since I feel it's a bit much to dump here, I put the code for the functions in a pastebin here.</a>
The first test I did was to build pascal's triangle to the 100th row. I used timeit to do this 100 times. The numbers below are the average time it took in seconds to build the triangle once.
<pre><code>gmpy2.gmpy2.comb 0.0012259269999998423
math.comb 0.007063110999999935
__main__.stdfactorial2 0.011469491
__main__.scipybinom 0.0120114319999999
__main__.stdfactorial 0.012105122
__main__.scipycombexact 0.012569045999999844
__main__.andrewdalke 0.01825201100000015
__main__.rabih 0.018472497000000202
__main__.kta 0.019374668000000383
__main__.wirawan 0.029312811000000067
scipy.special._basic.comb 0.03221609299999954
__main__.jfsmodifiedscipy 0.04332894699999997
__main__.rojas 0.04395155400000021
sympy.functions.combinatorial.factorials.binomial 0.3233529779999998
__main__.nasbanov 0.593365528
__main__.pantelis300 1.7780402499999999
</code></pre>
You may notice that there are only 16 functions here. That's because the <code>recursive()</code> function couldn't complete this even once in a reasonable amount of time, so I had to exclude it from the timeit tests. seriously, it's been going for hours.
I also timed various other types of inputs that not all of the above functions supported. Keep in mind that I only ran the test for each 10 times because nCr is computationally expensive and I'm impatient
Fractional values for n
<pre><code>__main__.scipybinom 0.011481370000000001
__main__.kta 0.01869513999999999
sympy.functions.combinatorial.factorials.binomial 6.33897291
</code></pre>
Fractional values for r
<pre><code>__main__.scipybinom 0.010960040000000504
scipy.special._basic.comb 0.03681254999999908
sympy.functions.combinatorial.factorials.binomial 3.2962564499999987
</code></pre>
Fractional values for n and r
<pre><code>__main__.scipybinom 0.008623409999998444
sympy.functions.combinatorial.factorials.binomial 3.690936439999999
</code></pre>
Negative values for n
<pre><code>gmpy2.gmpy2.comb 0.010770989999997482
__main__.kta 0.02187850000000253
__main__.rojas 0.05104292999999984
__main__.nasbanov 0.6153183200000001
sympy.functions.combinatorial.factorials.binomial 3.0460310799999943
</code></pre>
Negative fractional values for n, fractional values for r
<pre><code>sympy.functions.combinatorial.factorials.binomial 3.7689941699999965
</code></pre>
the best solution currently for maximum speed and versatility would be a hybrid function to choose between different algorithms depending on the inputs
<pre><code>def hybrid(n: typing.Union[int, float], k: typing.Union[int, float]) -&gt; typing.Union[int, float]:
 # my own custom hybrid solution
 def is_integer(n):
 return isinstance(n, int) or n.is_integer()
 if k &lt; 0:
 raise ValueError(&quot;k cannot be negative.&quot;)
 elif n == 0:
 return 0
 elif k == 0 or k == n:
 return 1
 elif is_integer(n) and is_integer(k):
 return int(gmpy2.comb(int(n), int(k)))
 elif n &gt; 0:
 return scipy.special.binom(n, k)
 else:
 return float(sympy.binomial(n, k))
</code></pre>
Since <code>sympy.binomial()</code> is so slow, the true ideal solution would be to combine the code of <code>scipy.special.binom()</code> which performs well for fractions and <code>gmpy2.comb()</code> which performs well for ints. <a href="https://github.com/scipy/scipy/blob/701ffcc8a6f04509d115aac5e5681c538b5265a2/scipy/special/orthogonal_eval.pxd#L67-L126" rel="nofollow noreferrer">scipy's func</a> and <a href="https://github.com/aleaxit/gmpy/blob/00ba694027e72aa629260032c3103feadff54c09/src/gmpy2_mpz_misc.c#L775-L828" rel="nofollow noreferrer">gympy2's func</a> are both written in C which I am not very familiar with.

I need to compute combinatorials (nCr) in Python but cannot find the function to do that in <code>math</code>, <code>numpy</code> or <code>stat</code> libraries. Something like a function of the type:

<pre><code>comb = calculate_combinations(n, r)
</code></pre>

I need the number of possible combinations, not the actual combinations, so <code>itertools.combinations</code> does not interest me.

Finally, I want to avoid using factorials, as the numbers I'll be calculating the combinations for can get too big and the factorials are going to be monstrous.

This seems like a REALLY easy to answer question, however I am being drowned in questions about generating all the actual combinations, which is not what I want.

Statistics: combinations in Python

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我需要在Python语言中计算组合(nCr)，但在math、numpy或stat库中找不到执行此操作的函数。类似于类型的函数：comb = calculate_combinations(n, r)我需要的是可能组合的数量，而不是实际组合的数量，所以我对itertools.combinations不感兴趣。最后，我想避免...

问统计信息: Python中的组合
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问统计信息: Python中的组合EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问统计信息: Python中的组合
EN