有效地计算组合和排列

Question

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

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

到目前为止，我已经提出了一个特殊情况来反映 nCr 的对称性，但我仍然想找到一个更好的算法来避免调用 factorial®，这是一个不必要的大中间结果。如果没有这种优化，最后一个 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)

原文由 Christian Oudard 发布，翻译遵循 CC BY-SA 4.0 许可协议

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

原文由 wich 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

两个相当简单的建议：

1. 为避免溢出，请在日志空间中执行所有操作。使用 log(a * b) = log(a) + log(b) 和 log(a / b) = log(a) - log(b) 这一事实。这使得处理非常大的阶乘变得容易：log(n! / m!) = log(n!) - log(m!) 等。

2. 使用伽玛函数而不是阶乘。您可以在 scipy.stats.loggamma 中找到一个。这是一种比直接求和更有效的计算对数阶乘的方法。 loggamma(n) == log(factorial(n - 1)) ，类似地， gamma(n) == factorial(n - 1) 。

原文由 dsimcha 发布，翻译遵循 CC BY-SA 2.5 许可协议