有效地计算组合和排列

我有一些代码来计算排列和组合，并且我正在努力使其更好地处理大量数字。

我找到了一种更好的排列算法，可以避免大量的中间结果，但我仍然认为我可以在组合方面做得更好。

到目前为止，我已经提出了一个特殊情况来反映 nCr 的对称性，但我仍然希望找到一种更好的算法来避免调用阶乘（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 离 r 不远，那么使用组合的递归定义可能会更好，因为 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

现在我们只需要使用带有reduce 的尾递归来应用递归步骤。我们从 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)