Python itertools permutations对于2的幂次方太慢了。

Question

我遇到了一个非常奇怪的问题，无法找到解决方法。

以下代码可以找到n的质因数分解，将质因数放入列表中，然后找到所有可能的总和变化方式并打印出该列表的唯一值。

例如：44的质因数为2*2*11，所以对于44，它会打印出：

2,2+2,11,2+11,2+2+11 = 2,4,11,13,15:

这是我的代码：

import math
import sys
import itertools
from itertools import permutations

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac


def primecombo(n):
    b = []
    for i in range(1, len(primes(n))+1):
        for subset in permutations(primes(n), i):
            b.append(sum((subset)))
    a = list(set(b))
    a.sort()
    return a

代码本身在大部分情况下似乎都能正常高效地运行，但是出现一个奇怪的问题：当你处理任何只有2为质因数的数字时，它会变得非常慢。

如果你尝试打印primecombo(444444)或primecombo(23452823)，它会几乎瞬间打印出结果，但是如果你尝试2048或4096，它就会变得非常缓慢。

有人能看出这种情况的原因并且告诉我该如何修复吗？

- Anonymous

---

23452823只有7个因子，而2048有11个。由于获取排列是指数级的，所以它会变得难以忍受地更长。此外，在每次迭代中重新计算质数，应将它们存储在一个变量中。 - Olivier Melançon

此外，您不需要对质数进行排列，只需要组合即可。这应该会显著提高您的时间效率。 - Olivier Melançon

谢谢Olivier，这显著加快了事情的进展。 - Anonymous

如果一个因子出现了多次，可以使用因子计数器并在其组合上进行迭代来进一步加快速度。如果没有人回答，我稍后会写一个完整的答案。 - Olivier Melançon

Answer 1

简短回答

使用 itertools.permutations 会使你的算法计算冗余的质因数分区。使用 itertools.combinations 可以得到显著的改进，但我们仍然可以做得更好。

详细回答

使用 itertools.permutations 查找所有排列会使你的函数 primecombo 的运行时间与因子数量成阶乘关系，比指数还要糟糕。

让我们来看看与因子数量 k 相关的时间复杂度。主要步骤是迭代 permutations(primes(n), len(primes(n))。有 k! 种排列，你正在求和每个排列。因此，你的算法的时间复杂度为

O(k * k!)

这就是为什么处理因子数量为 11 的 2048 比处理因子数量为 7 的 23452823 要难以承受。

替代方案

幸运的是，不必访问每个排列。例如，如果你有因子 2、3 和 4，则将对 2、3 和 4 的每个排列求和是多余的。一个快速的改进是求和组合，但即使这样，当有出现多次的因子时，我们有时也会计算两次相同的分区。

以下解决方案通过使用 Counter 而不是 list 跟踪质因数来解决了这个问题。这随后允许我们使用 itertools.product。

这个算法能够在几毫秒内找到你需要的 4096 的总和，请参见下面的时间复杂度分析。

import itertools
from collections import Counter

def primes(n):
    primfac = Counter()
    d = 2

    while d ** 2 <= n:
        while (n % d) == 0:
            primfac[d] += 1
            n //= d
        d += 1

    if n > 1:
       primfac[n] += 1

    return primfac

def primecombo(n):
    factor_sums = [[p * e for e in range(exp + 1)] for p, exp in primes(n).items()]

    sums = set(sum(partition) for partition in itertools.product(*factor_sums))

    return sums

primecombo(4096) # {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24}

时间复杂度

时间复杂度取决于您的质因数分布情况。最坏情况是有k个不同的因子。我们的itertools.product的大小为2^k，因此使该算法的时间复杂度为

O(k * 2^k)

请注意，以上内容中的HTML标签已被保留。

- Olivier Melançon

---

请问您能否在您的优秀答案中添加OP原始代码和您的代码的运行时间？ - Gabriel