按总和顺序生成组合

Question

Itertools组合好像是按照字典顺序出来的：

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

但我想按总和最大的顺序生成它们：

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

实际上全部生成它们并且无法排序，因为结果太大（这是一个较小的例子）。

我认为可以将 docs 中提供的配方修改为“大致等效”的 python 代码：

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)

但想不通。

如果有帮助，r 将始终为 2，并且输入足够小，可以将其排序到单调非递减列表中。

Answer 1

反向排序。然后每个数字可以与所有后面的数字配对，提供具有非升序和的对序列。合并所有这些序列。

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))

替代版本，玩转迭代工具：

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))