将整数写为不同整数的 k 次方之和

Question

给定一个整数 n (n >= 1) 和一个数字 k，返回将 n 写为 k 次方不同整数的所有可能方法。例如，如果 n = 100 且 k = 2：

100 = 1**2 + 3**2 + 4**2 + 5**2 + 7**2
    = 6**2 + 8**2
    = 10**2

或者如果 k = 3：

100 = 1**3 + 2**3 + 3**3 + 4**3

因此program(100,2)返回类似[(2, [1, 3, 4, 5, 7]), (2, [6, 8]), (2, [10])], and 的内容program(100,3) [(3, [1, 2, 3, 4])]。

只要输入 n 很小，或者 k 是“大”（>=3），一切都会正常工作。我的方法是首先获取所有整数的列表，其 k 次幂 <= n。

def possible_powers(n,k):
    arr,i = [],1
    while i**k <= n:
        arr.append(i)
        i += 1
    return arr

然后（这是错误），我创建了该列表的所有子集（作为列表）：

def subsets(L):
    subsets = [[]]
    for i in L:
        subsets += [subset+[i] for subset in subsets]
    return subsets

最后，我循环遍历所有这些子集，将每个元素求 k 次方并将它们相加，仅选择加起来为 n 的元素。

def kth_power_sum(arr,k):
    return sum([i**k for i in arr])

def solutions(n,k):
    return [(k,i) for i in subsets(possible_powers(n,k)) if kth_power_sum(i,k) == n]

我知道问题出在子集创建上，但我不知道如何优化它。就像，如果我尝试解决方案（1000,2），它会创建一个大集合，占用超过 4GB 内存。我的猜测是筛出一些子集，但这没有多大帮助，除非我有一个非常有效的筛子。

任何帮助是极大的赞赏。如果有不清楚的地方，或者我在发布此内容时犯了一个错误，请告诉我。

Answer 1

如果将其实现为递归生成器，则不需要存储大量值（甚至不需要存储结果）：

\n

def powersum(n,k,b=1):\n    bk = b**k\n    while bk < n:\n        for bases in powersum(n-bk,k,b+1):\n            yield [b]+bases\n        b += 1\n        bk = b**k\n    if bk == n :\n        yield [b]\n        \nprint(*powersum(100,2)) # [1, 3, 4, 5, 7] [6, 8] [10]\nprint(*powersum(100,3)) # [1, 2, 3, 4]\nprint(sum(1 for _ in powersum(1000,2))) # 1269 solutions\nprint(sum(1 for _ in powersum(2000,2))) # 27526 solutions (6 seconds)     \n

\n

请注意，这仍然具有指数时间复杂度，因此对于稍大的 n 值，它会慢得多

\n

print(sum(1 for _ in powersum(2200,2))) # 44930 solutions (12 seconds)\nprint(sum(1 for _ in powersum(2500,2))) # 91021 solutions (25 seconds)\nprint(sum(1 for _ in powersum(2800,2))) # 175625 solutions (55 seconds)\nprint(sum(1 for _ in powersum(3100,2))) # 325067 solutions (110 seconds)\n

\n

[编辑]\xc2\xa0供将来参考，这里是 Kelly Bundy 的缓存版本，运行速度要快得多。将其发布在这里以防他的演示链接被破坏：

\n

from functools import cache\nfrom time import time\n\n@cache                  \ndef powersum(n,k,b=1):\n    bk = b**k\n    res = []\n    while bk < n:\n        for bases in powersum(n-bk,k,b+1):\n            res.append([b]+bases)\n        b += 1\n        bk = b**k\n    if bk == n :\n        res.append([b])\n    return res\n

\n

注意：虽然缓存会消耗一些内存，但它的大小远不及所有可能组合的完整幂集的大小。

\n