Generating combinations in order of their sum

Question

Itertools combinations seem to come out in lexicographic order:

>>> for c in combinations([9,8,7,2,2,1], 2):
...     print(c, sum(c))
... 
(9, 8) 17
(9, 7) 16
(9, 2) 11
(9, 2) 11
(9, 1) 10
(8, 7) 15
(8, 2) 10
(8, 2) 10
(8, 1) 9
(7, 2) 9
(7, 2) 9
(7, 1) 8
(2, 2) 4
(2, 1) 3
(2, 1) 3

But I want to generate them in order of greatest sum:

>>> for c in sorted(combinations([9,8,7,2,2,1], 2), key=sum, reverse=True):
...     print(c, sum(c))
... 
(9, 8) 17
(9, 7) 16
(8, 7) 15
(9, 2) 11
(9, 2) 11
(9, 1) 10
(8, 2) 10
(8, 2) 10
(8, 1) 9
(7, 2) 9
(7, 2) 9
(7, 1) 8
(2, 2) 4
(2, 1) 3
(2, 1) 3

Actually generating them all and sorting is not possible because the result is too large (this is a smaller example).

I thought it might be possible to modify the recipe offered in the docs as "roughly equivalent" python code:

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

But could not figure it out.

If it helps, r will always be 2 and the input (~10k elements) is small enough that it could be sorted to a monotonically non-increasing list.

There's also a rejection criteria that is expensive to compute. So it's not just the first combo which is selected, but the largest combo (by sum) that was not rejected after checking another condition. The vast majority of combos are rejected - we'll have to go through about 0.1% of them before finding one that is not rejected.

Answer 1

Sort in reverse. Then each number can be paired with all later numbers, providing a sequence of pairs with non-ascending sums. Merge all these sequences.

from heapq import merge

def combinations(xs):
    xs.sort(reverse=True)
    def pairs(ix):
        i, x = ix
        for j in range(i+1, len(xs)):
            yield x, xs[j]
    return merge(
        *map(pairs, enumerate(xs)),
        key=sum,
        reverse=True
    )

for c in combinations([9,8,7,2,2,1]):
    print(c, sum(c))

Alternative version, having fun with iteration tools:

from heapq import merge
from itertools import repeat
from copy import copy

def combinations(xs):
    xs.sort(reverse=True)
    it = iter(xs)
    return merge(
        *map(zip,
             map(repeat, it),
             map(copy, repeat(it))),
        key=sum,
        reverse=True
    )

for c in combinations([9,8,7,2,2,1]):
    print(c, sum(c))