有效地计算组合和排列

如果n离r不远,那么使用组合的递归定义可能更好,因为xc0==1,您将只有几个迭代:

这里的相关递归定义是:

n c r=(n-1)c(r-1)*n/r

这可以通过以下列表使用尾部递归很好地计算出来:

[(n-r,0),(n-r+1,1),(n-r+2,2),…,(n-1,r-1),(n,r)]

当然,它很容易在python中生成(我们省略了nc0=1以来的第一个条目)。 izip(xrange(n - r + 1, n+1), xrange(1, r+1)) 请注意,这假设r<=n,您需要检查并交换它们(如果没有)。如果R<N/2,则R=N-R,也可优化使用。

现在我们只需要使用带reduce的tail递归来应用递归步骤。我们从1开始,因为nc0是1,然后将当前值与列表中的下一个条目相乘,如下所示。

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)

两个相当简单的建议:

1. 为避免溢出,请在日志空间中执行所有操作。使用日志(A*B)=Log(A)+Log(B)和Log(A/B)=Log(A)-Log(B)这一事实。这使得使用非常大的阶乘很容易:log(n!m)= log(n!)-日志(m!)等。

2. 使用gamma函数而不是factorial。你可以在里面找到一个 scipy.stats.loggamma . 这是一种比直接求和更有效的计算对数因子的方法。 loggamma(n) == log(factorial(n - 1)) 和类似的, gamma(n) == factorial(n - 1) .

如果您不需要纯Python解决方案, gmpy2 可能会有帮助( gmpy2.comb 非常快)。

在scipy中有一个函数,这个函数还没有提到: scipy.special.comb . 根据你的医生测试的一些快速计时结果(大约0.004秒 comb(100000, 1000, 1) == comb(100000, 99000, 1) )

[虽然这个特定的问题似乎是关于算法的问题 is there a math ncr function in python 标记为此的副本…]

如果您的问题不需要知道排列或组合的确切数目,那么您可以使用 Stirling's approximation 对于阶乘。

这将导致如下代码:

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(n-r) if n>20 else
            math.factorial(n)/math.factorial(n-r))

def ncr(n,r):    
    return (stirling(n)/stirling(r)/stirling(n-r) if n>20 else
            math.factorial(n)/math.factorial(r)/math.factorial(n-r))

print(npr(3,2))
# 6
print(npr(100,20))
# 1.30426670868e+39
print(ncr(3,2))
# 3
print(ncr(100,20))
# 5.38333246453e+20

如果您正在计算n choose k(我认为您正在使用ncr),那么有一个动态编程解决方案可能会更快。这将避免使用阶乘,另外,如果希望以后使用,还可以保留表。

以下是它的教学链接:

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

不过,我不确定如何更好地解决你的第一个问题,对不起。

编辑:这是模型。有一些相当搞笑的一次性错误,所以它肯定能忍受一些更干净。

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,n-i):
        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]

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

应该允许您计算组合

更有效的NCR解决方案-空间和精度方面。

中介(Res)保证始终为int,且不会大于结果。空间复杂度是O(1)(没有列表,没有压缩文件,没有堆栈),时间复杂度是O(R)-正是R乘和R除。

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

使用 xrange() 而不是 range() 由于没有中间列表被创建、填充、迭代,然后被销毁,这将稍微加快速度。也, reduce() 具有 operator.mul .

对于n,选择k,可以使用帕斯卡三角形。基本上,您需要保留大小为n的数组来计算所有n选择k值。只需要添加。

您可以输入两个整数并导入数学库以查找阶乘,然后应用ncr公式

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

from numpy import prod

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