带权重的位掩码

下面代码背后的想法是枚举排序后的组合 递归（好吧，不使用递归）作为对列表的尾部， 然后在使用较小 元素和使用较大 元素。空间需求最小化 发生器（一般应按元件数量量级排列 你拿）。

import collections
import itertools


def extend_sorted(pair, sequence):
    argmin_pair = min(range(2), key=pair.__getitem__)
    min_pair = pair[argmin_pair]
    argmax_pair = 1 - argmin_pair
    max_pair = pair[argmax_pair]
    buffer = collections.deque()
    for sub_combo, sub_total in sequence:
        while buffer and buffer[0][1] < min_pair + sub_total:
            yield buffer.popleft()
        yield ([argmin_pair] + sub_combo, min_pair + sub_total)
        buffer.append(([argmax_pair] + sub_combo, max_pair + sub_total))
    while buffer:
        yield buffer.popleft()


def enumerate_least_sums(pairs):
    sequence = [([], 0)]
    for pair in reversed(pairs):
        sequence = extend_sorted(pair, sequence)
    for combo, total in sequence:
        yield combo


if __name__ == "__main__":
    print(*itertools.islice(enumerate_least_sums([(1, 9), (5, 5), (6, 4), (2, 8)]), 5))

输出：

[0, 0, 1, 0] [0, 1, 1, 0] [0, 0, 0, 0] [0, 1, 0, 0] [0, 0, 1, 1]