python - 通过最小和生成整数组合

Question

我的问题源于生成一个非常大的素数排序列表的唯一组合选择 5，但我需要返回这些组合，以便首先返回总和最小的组合。 python itertools.combinations() 函数返回数字，增加最后一个，直到它到达可迭代对象的末尾，然后再增加下一个，等等。这不适合我的项目，因为总和将继续增加直到它到达我的素数集的最后一个元素，此时总和将下降，然后再次增加。

例如，如果我有一小组素数 {2,3,5,7,11,13,17,19,23,29}，我需要的组合是按此顺序返回:

    (2, 3, 5, 7, 11)    sum = 28
    (2, 3, 5, 7, 13)    sum = 30
    (2, 3, 5, 7, 17)    sum = 34
    (2, 3, 5, 11, 13)   sum = 34
    (2, 3, 5, 7, 19)    sum = 36
    (2, 3, 7, 11, 13)   sum = 36
    (2, 3, 5, 11, 17)   sum = 38
    (2, 5, 7, 11, 13)   sum = 38
    (3, 5, 7, 11, 13)   sum = 39
    (2, 3, 5, 7, 23)    sum = 40
    (2, 3, 5, 11, 19)   sum = 40
    (2, 3, 5, 13, 17)   sum = 40
    (2, 3, 7, 11, 17)   sum = 40
    (2, 3, 5, 13, 19)   sum = 42
    (2, 3, 7, 11, 19)   sum = 42
    (2, 3, 7, 13, 17)   sum = 42
    (2, 5, 7, 11, 17)   sum = 42
    ...

具有相同总和的两个集合的顺序无关紧要，只要生成器返回的总和较大的集合不会先于总和较小的集合返回即可。我正在处理的素数集包含大约 100,000 个元素，这意味着简单地生成所有组合并对它们进行排序是非常不可行的，因为它需要空间容纳 83,325,000,291,662,500,020,000 个元组，每个元组包含 5 个整数。此外，返回的组合元组中的每个元素都必须是唯一的；不能有重复的整数。有什么想法吗？

Answer 1

与其生成组合并对它们求和，不如尝试相反的方法 - 给定一个和序列，为每个和生成组合:

# some primes for tesing
primes = [2]
x = 3
while x < 100000:
    if all(x % p for p in primes):
        primes.append(x)
    x += 2

# main code

def find(tsum, tlen):

    def _find(tsum, tlen, path, idx):
        if tlen <= 0:
            if tsum == 0:
                yield path
            return
        while True:
            p = primes[idx]
            if p > tsum:
                return
            for f in _find(tsum - p, tlen - 1, path + [p], idx + 1):
                yield f
            idx += 1

    return _find(tsum, tlen, [], 0)

for s in range(1001, 1002): # just for testing, should be range(28, max possible sum)
    for comb in find(s, 5):
        print s, comb

这在性能方面远非理想，但在我的机器上仍然相当快。