Generate combinations of integers by least sum

Question

My issue stems from generating unique combinations of a very large sorted list of prime numbers choose 5, but I need the combinations to be returned such that the combinations with the smallest sums are returned first. The python itertools.combinations() function returns the numbers, increasing the final one until it reaches the end of the iterable object before increasing the next one, etc. This is unsuitable for my project because the sum will continue to increase until it reaches the final element of my set of primes, at which point the sum will drop before increasing again.

For instance, if I have a small set of primes {2,3,5,7,11,13,17,19,23,29}, I would need the combinations to be returned in this order:

    (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
    ...

The order of two sets with the same sum doesn't matter, just as long as a set with a greater sum is not returned by a generator before a set with a lesser sum. The set of primes I'm working with contains approximately 100,000 elements, meaning simply generating all combinations and sorting them is incredibly infeasible, as it would require space for 83,325,000,291,662,500,020,000 tuples of 5 integers each. Furthermore, each element in the returned tuple of combinations must be unique; there can be no repeated integers. Any ideas?

Answer 1

Instead of generating combinations and summing them, try it the other way round - given a sequence of sums, generate combinations for each sum:

# 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

This is far from ideal in terms of performance, but still quite fast on my machine.