统计信息: Python中的组合
统计信息: Python中的组合
提问于 2010-06-12 02:13:17
我需要在Python语言中计算组合(nCr)，但在math、numpy或stat库中找不到执行此操作的函数。类似于类型的函数：
comb = calculate_combinations(n, r)我需要的是可能组合的数量，而不是实际组合的数量，所以我对itertools.combinations不感兴趣。
最后，我想避免使用阶乘，因为我要计算组合的数字可能会变得太大，阶乘会变得非常可怕。
这似乎是一个很容易回答的问题，然而我被有关生成所有实际组合的问题淹没了，这不是我想要的。
回答 16
Stack Overflow用户
回答已采纳
发布于 2010-06-12 02:29:58
请参见scipy.special.comb (旧版本的scipy中的scipy.misc.comb)。当exact为False时，它使用gammaln函数来获得良好的精度，而不需要花费太多时间。在确切的情况下，它返回一个任意精度的整数，这可能需要很长时间来计算。
Stack Overflow用户
发布于 2010-06-12 09:25:41
为什么不自己写呢？这是一行或类似的：
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) )测试打印帕斯卡三角形：
>>> 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
>>> PS。经过编辑，将int(round(reduce(mul, (float(n-i)/(i+1) for i in range(k)), 1)))替换为int(reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1))，因此它不会在大N/K时出错
Stack Overflow用户
发布于 2010-06-12 03:12:12
在谷歌代码上快速搜索一下(它使用了@Mark Byers's answer中的公式)：
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) + 1):
ntok *= n
ktok *= t
n -= 1
return ntok // ktok
else:
return 0如果你需要一个确切的答案，choose()比scipy.misc.comb()快10倍(在所有0 <= (n，k) < 1e3对上进行了测试)。
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+1L):
val /= n
n += 1
return val页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3025162
复制相关文章
相似问题