python - 如何按总和的顺序遍历大量整数元组？

Question

我正在使用 itertools.combinations()迭代整数元组。

我对满足某些条件的最低总和的元组感兴趣:

def findLowestNiceTuple:
    for tup in itertools.combinations(range(1, 6), 2):
        if niceTuple(tup):
            return tup

生成器的默认顺序不是元素总和的顺序。例如:

>>> itertools.combinations(range(1, 6), 2)

提供一个生成器，它将生成以下元素:

[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]

如您所见，(1, 5) 的总和大于 (2,3) 的总和。对于提前终止，我需要顺序为 ..., (1, 4), (2, 3), (1, 5), ... 的元组。

对于少量的组合，您可以使用 sorted() 来解决这个问题:

>>> sorted(itertools.combinations(range(1, 6), 2), key=sum)
[(1, 2), (1, 3), (1, 4), (2, 3), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]

但是，sorted() 将生成器转换为一个完全保存在内存中的列表。这意味着它不再很好地扩展。像 itertools.combinations(range(1, 600), 400) 这样的东西将不可避免地产生一个 MemoryError。

有没有一种内存更友好的方式来达到预期的结果？

PS:我确实意识到完全迭代我提到的最后一个序列需要很长时间，但我正在寻找的元组应该非常接近开始。如果我可以指望订单，我可以像在第一个片段中那样提前终止。

Answer 1

下面是我的解决方法，使用递归函数查找总和为给定值的所有组合:

def ordered_combinations(pop, n):
    pop = sorted(pop)

    for s in range(sum(pop[:n]), sum(pop[-n:])+1):
        yield from get_sums(pop, s, n)

def get_sums(pop, s, n):
    if n == 1:
        if s in pop:
            yield [s]
        return

    for i, v in enumerate(pop):
        if sum(pop[i:i+n]) > s:
            return
        for rest in get_sums(pop[i+1:], s-v, n-1):
            rest.append(v)
            yield rest

这是它的输出示例:

>>> for c in ordered_combinations(range(1, 8), 4):
    print(c, sum(c))


[4, 3, 2, 1] 10
[5, 3, 2, 1] 11
[6, 3, 2, 1] 12
[5, 4, 2, 1] 12
[7, 3, 2, 1] 13
[6, 4, 2, 1] 13
[5, 4, 3, 1] 13
[7, 4, 2, 1] 14
[6, 5, 2, 1] 14
[6, 4, 3, 1] 14
[5, 4, 3, 2] 14
[7, 5, 2, 1] 15
[7, 4, 3, 1] 15
[6, 5, 3, 1] 15
[6, 4, 3, 2] 15
[7, 6, 2, 1] 16
[7, 5, 3, 1] 16
[6, 5, 4, 1] 16
[7, 4, 3, 2] 16
[6, 5, 3, 2] 16
[7, 6, 3, 1] 17
[7, 5, 4, 1] 17
[7, 5, 3, 2] 17
[6, 5, 4, 2] 17
[7, 6, 4, 1] 18
[7, 6, 3, 2] 18
[7, 5, 4, 2] 18
[6, 5, 4, 3] 18
[7, 6, 5, 1] 19
[7, 6, 4, 2] 19
[7, 5, 4, 3] 19
[7, 6, 5, 2] 20
[7, 6, 4, 3] 20
[7, 6, 5, 3] 21
[7, 6, 5, 4] 22

组合总是首先产生最大的值，作为我将它们构建为列表的方式的产物(通过在末尾附加小值，而不是通过连接到前面)。如果你想让它们从小到大排序，你可以改变 rest.append(v); yield rest 行到 yield [v]+rest。

该代码使用了 Python 3.3 引入的 yield from 语法。如果您使用的是不支持该功能的早期版本，则可以使用以下等效代码:

for v in get_sums(pop, s, n):
    yield v

该代码甚至可以处理您描述的从 800 个成员范围中提取的 400 个组合的极端情况。这是该计算的前 20 个结果(只显示了它们最大的 10 个值，因为其余的都是相同的 390 到 1)，以及它们的总和:

>>> for i, v in enumerate(ordered_combinations(range(1, 800), 400)):
    if i >= 20:
        break
    print(v[:10], sum(v))


[400, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80200
[401, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80201
[402, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80202
[401, 400, 398, 397, 396, 395, 394, 393, 392, 391] 80202
[403, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80203
[402, 400, 398, 397, 396, 395, 394, 393, 392, 391] 80203
[401, 400, 399, 397, 396, 395, 394, 393, 392, 391] 80203
[404, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80204
[403, 400, 398, 397, 396, 395, 394, 393, 392, 391] 80204
[402, 401, 398, 397, 396, 395, 394, 393, 392, 391] 80204
[402, 400, 399, 397, 396, 395, 394, 393, 392, 391] 80204
[401, 400, 399, 398, 396, 395, 394, 393, 392, 391] 80204
[405, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80205
[404, 400, 398, 397, 396, 395, 394, 393, 392, 391] 80205
[403, 401, 398, 397, 396, 395, 394, 393, 392, 391] 80205
[403, 400, 399, 397, 396, 395, 394, 393, 392, 391] 80205
[402, 401, 399, 397, 396, 395, 394, 393, 392, 391] 80205
[402, 400, 399, 398, 396, 395, 394, 393, 392, 391] 80205
[401, 400, 399, 398, 397, 395, 394, 393, 392, 391] 80205
[406, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80206

因为它是递归的，所以如果您请求 1000 次组合，此代码可能会失败(这是由于 Python 的默认递归限制)。如有必要，您可以使用 sys.setrecursionlimit 修改它的限制。

如果您对非常大的人口进行深入研究，它也可能会出现内存问题，因为 get_sums 在递归步骤中对人口进行切片(并因此进行复制)。如果您对该代码的使用将仅使用 range，您可以通过从 ordered_combinations< 中删除 pop = sorted(pop) 行来解决内存问题，因为 Python 3 的 range 对象可以有效地切片(即 range(1,100)[10:] 是 range(11,100)).