2 的幂的 python itertools 排列太慢

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 的数字时，它会变得非常慢。

如果您尝试 print primecombo(444444) 或 print primecombo(23452823)，它几乎会立即打印结果，但如果您尝试 2048 或 4096，它会变得非常非常慢。

谁能看出为什么会这样，我能做些什么来解决这个问题？

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)