我有一些代码来算排列组合，我试图使它的大量工作得更好。
我发现一种避免大的中间结果的排列更好的算法，但我仍然认为我可以做的更好的组合。
到目前为止，我已经把在特殊情况下，以反映无碳复写纸的对称性，但我还是想找到一个更好的算法，避免了调用阶乘（R），这是一个不必要的大中间结果。如果没有这种优化，最后文档测试时间过长尝试计算阶乘（99000）。
任何人都可以提出一个更有效的方法来计算组合？
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)
如果n不远处，则成为使用组合的递归定义可能是更好的，因为XC0 == 1，你只会有几个迭代：
这里的相关递归定义是：
nCr的=（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 =正 - 河
现在，我们只需要使用尾递归以减少应用递归步骤。我们先从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)
使用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)
两个非常简单的建议：
scipy.stats.loggamma。这是一种更有效的方式来计算数的阶乘比直接总和。 loggamma(n) == log(factorial(n - 1))，同样，gamma(n) == factorial(n - 1)。还有哪些尚未提到这SciPy的功能：scipy.special.comb。它基于对您的文档测试一些快速时序结果（〜0.004秒为comb(100000, 1000, 1) == comb(100000, 99000, 1)）似乎有效。
[虽然这个具体的问题似乎是关于算法的问题is there a math ncr function in python被标记为这个副本...]
如果你并不需要一个纯Python的解决方案，gmpy2可能帮助（gmpy2.comb是非常快的）。
如果您的问题并不需要知道的排列组合或的确切数字，那么你可以使用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
如果您是计算ñ选择K（这是我认为你与NCR做的），有一个动态编程解决方案，可能会快很多。这将避免阶乘，再加上你可以保持桌面，如果你想以备后用。
这里是一个教学环节吧：
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/dyprog.html
我不确定如何更好地解决你的第一个问题，虽然，对不起。
编辑：这是实体模型。有一些很搞笑的off-by-一个错误，所以它肯定能站多一些清理。
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
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))