有效地计算组合和排列

Question

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

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

到目前为止，我已经放置了一个特殊情况来反映 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)

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)

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

Answer 3

scipy 中有一个尚未提及的函数：scipy.special.comb。根据 doctest 的一些快速计时结果，它似乎很有效（comb(100000, 1000, 1) == Comb(100000, 99000, 1) 的时间约为 0.004 秒)。

[虽然这个具体问题似乎与算法有关，但问题 python 中是否有数学 ncr 函数 被标记为与此重复...]

Answer 4

对于 Python 3.7 之前的版本：

def prod(items, start=1):
    for item in items:
        start *= item
    return start


def perm(n, k):
    if not 0 <= k <= n:
        raise ValueError(
            'Values must be non-negative and n >= k in perm(n, k)')
    else:
        return prod(range(n - k + 1, n + 1))


def comb(n, k):
    if not 0 <= k <= n:
        raise ValueError(
            'Values must be non-negative and n >= k in comb(n, k)')
    else:
        k = k if k < n - k else n - k
        return prod(range(n - k + 1, n + 1)) // math.factorial(k)

---

对于 Python 3.8+：

• math.perm( )
• math.comb()

---

有趣的是，组合函数的一些手动实现可能比 math.comb() 更快：

def math_comb(n, k):
    return math.comb(n, k)


def comb_perm(n, k):
    k = k if k < n - k else n - k
    return math.perm(n, k) // math.factorial(k)


def comb(n, k):
    k = k if k < n - k else n - k
    return prod(range(n - k + 1, n + 1)) // math.factorial(k)


def comb_other(n, k):
    k = k if k > n - k else n - k
    return prod(range(n - k + 1, n + 1)) // math.factorial(k)


def comb_reduce(n, k):
    k = k if k < n - k else n - k
    return functools.reduce(
        lambda x, y: x * y[0] // y[1],
        zip(range(n - k + 1, n + 1), range(1, k + 1)),
        1)


def comb_iter(n, k):
    k = k if k < n - k else n - k
    result = 1
    for i in range(1, k + 1):
        result = result * (n - i + 1) // i
    return result


def comb_iterdiv(n, k):
    k = k if k < n - k else n - k
    result = divider = 1
    for i in range(1, k + 1):
        result *= (n - i + 1)
        divider *= i
    return result // divider


def comb_fact(n, k):
    k = k if k < n - k else n - k
    return math.factorial(n) // math.factorial(n - k) // math.factorial(k)

所以实际上 comb_perm() （使用 math.perm() 和 math.factorial() 实现）实际上比大多数的 math.comb() 更快这些基准的时间，显示固定 n=256 和增加 k（直到 k = n // 2）的计算时间。

请注意，comb_reduce() 速度相当慢，但本质上与 @wich 的答案，而 comb_iter() 也相对较慢，本质上与 @ZXX 的答案。

此处进行部分分析（不含 comb_math()< /code> 和 comb_perm() 因为它们在 Colab 的 Python 版本（3.7）中不受支持（截至上次编辑）。

Answer 5

如果您不需要纯 python 解决方案，gmpy2 可能会有所帮助（gmpy2 .comb 非常快）。

Answer 6

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

中介 (res) 保证始终为 int 并且永远不会大于结果。空间复杂度为 O(1)（无列表、无 zip、无堆栈），时间复杂度为 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

Answer 7

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

应该允许你计算组合

Answer 8

如果您正在计算 N 选择 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]

Answer 9

如果您的问题不需要知道排列或组合的确切数量，那么您可以使用斯特林近似< /a> 为阶乘。

这会导致这样的代码：

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

Answer 10

使用 xrange() 代替 range() 会稍微加快速度，因为不会创建、填充、迭代然后销毁中间列表。此外，还有 reduce() 和 operator.mul。

Answer 11

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

Answer 12

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

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

Answer 13

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))

Answer 14

很简单。只需从 math 模块导入 comb 和 perm 函数即可获得结果！

完整代码如下：

from math import comb, perm
n, r =12, 3
print(comb(n,r), perm(n,r))