如何按整数的和的顺序迭代大量的整数元组？

Question

我使用^{}来迭代整数元组。在

我对满足某些条件的最小和的元组感兴趣：

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

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

^{pr2}$

给出一个发电机，它将产生以下元素：

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

下面是它的输出示例：

^{pr2}$

组合总是首先以最大的值生成，作为我如何将它们构建为列表的一个工件（通过在末尾附加小值，而不是通过连接到前面）。如果您希望它们从最小到最大排序，可以将rest.append(v); yield rest行改为yield [v]+rest。在

代码使用python3.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切片（并因此复制）了填充。如果您只使用ranges，那么您可能可以通过删除ordered_combinations中的pop = sorted(pop)行来解决内存问题，因为python3的range对象可以有效地切片（即，range(1,100)[10:]是{}）。在