生成无限序列的有序元组

Question

我有两个生成器genA和{}，它们各自生成一个无限的严格单调递增的整数序列。在

现在我需要一个生成器来生成所有元组(a, b)，这样a由genA生成，b由{}和{}生成，按a + b升序排列。在不明确的情况下，排序是不重要的，即如果a + b == c + d，那么它是先生成(a, b)还是先生成{}并不重要。在

例如。如果genA和genB都生成质数，那么新的生成器应该生成：

(2, 3), (2, 5), (3, 5), (2, 7), (3, 7), (5, 7), (2, 11), ...

如果genA和{}是有限列表，那么压缩和排序就可以了。在

显然，对于(x, b)形式的所有元组，以下内容都成立：first(genA) <= x <= max(genA,b) <= b，是first(genA)由{}生成的第一个元素，max(genA,b)是{}生成的最后一个元素，它小于b。在

我已经走了这么远。有什么办法把两台发电机按上述方式组合起来吗？在

Answer 1

我认为不保存genA的所有结果是不可能做到这一点的。解决方案可能如下所示：

import heapq
def gen_weird_sequence(genA, genB):
    heap = []
    a0 = next_a = next(genA)
    saved_a = []
    for b in genB:
        while next_a < b:
            saved_a.append(next_a)
            next_a = next(genA)
        # saved_a now contains all a < b
        for a in saved_a:
            heapq.heappush(heap, (a+b, a, b)) #decorate pair with sorting key a+b
        # (minimum sum in the next round) > b + a0, so yield everything smaller
        while heap and heap[0][0] <= b + a0:
            yield heapq.heappop(heap)[1:] # pop smallest and undecorate

说明：主循环只迭代genB中的所有元素，然后从genA中获取小于b的所有元素并将它们保存在一个列表中。然后它生成所有元组(a0, b), (a1, b), ..., (a_n, b)，并将它们存储在min-heap中，当您只对提取集合的最小值感兴趣时，这是一种有效的数据结构。与排序一样，可以执行trick操作，不保存对本身，而是在它们前面加上要排序的值（a+b），因为元组之间的比较将从比较第一项开始。最后，它从堆中弹出所有元素，这些元素的总和保证小于为下一个b生成的任何对的总和，并生成它们。在

注意，heap和{}在生成结果时都会增加，我猜这与到目前为止生成的元素数量的平方根成比例。在

用一些素数快速测试：

^{pr2}$

一如预期。无限发电机测试：

In [11]: from itertools import *
In [12]: list(islice(gen_weird_sequence(count(), count()), 16))
Out[12]: [(0, 1), (0, 2), (0, 3), (1, 2), (0, 4), (1, 3), (0, 5), (1, 4),
          (2, 3), (0, 6), (1, 5), (2, 4), (0, 7), (1, 6), (2, 5), (3, 4)]