python - 有效地计算组合和排列

Question

我有一些代码来计算排列和组合，我正在努力让它更好地处理大数。

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

到目前为止，我已经放入了一个特殊情况来反射(reflect) nCr 的对称性，但我仍然想找到一个更好的算法来避免调用 factorial(r)，这是一个不必要的大中间结果。如果没有这种优化，最后一个 doctest 会花费很长时间来计算阶乘 (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)

Answer 1

如果 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 中通过 izip(xrange(n - r + 1, n+1), xrange(1, r+1)) 生成(因为 nC0 = 1，我们省略了第一个条目) 请注意，这假设 r <= n 你需要检查并交换它们，如果它们不是。如果 r < n/2 then r = n - 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)