我的问题源于生成非常大的质数列表选择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个整数的元组的空间.此外,返回的组合元组中的每个元素都必须是唯一的.不能有重复的整数.有任何想法吗？

解决方法:

与其生成组合并求和,不如尝试另一种方法-给定一系列求和,为每个求和生成组合：

# 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

就性能而言,这远非理想,但在我的机器上仍然相当快.