我需要在Python语言中计算组合(nCr),但在math
、numpy
或stat
库中找不到执行此操作的函数。类似于类型的函数:
comb = calculate_combinations(n, r)
我需要的是可能组合的数量,而不是实际组合的数量,所以我对itertools.combinations
不感兴趣。
最后,我想避免使用阶乘,因为我要计算组合的数字可能会变得太大,阶乘会变得非常可怕。
这似乎是一个很容易回答的问题,然而我被有关生成所有实际组合的问题淹没了,这不是我想要的。
发布于 2010-06-12 02:29:58
请参见scipy.special.comb (旧版本的scipy中的scipy.misc.comb)。当exact
为False时,它使用gammaln函数来获得良好的精度,而不需要花费太多时间。在确切的情况下,它返回一个任意精度的整数,这可能需要很长时间来计算。
发布于 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时出错
发布于 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
https://stackoverflow.com/questions/3025162
复制相似问题