4

我有两个生成器genA，genB每个生成器都生成一个无限的、严格单调递增的整数序列。

现在我需要一个生成器来生成所有元组，这些元组(a, b)由aandgenA产生，并且由andb产生，按升序排序。在不明确的情况下，排序无关紧要，即如果，它是先生成还是先生成都没有关系。genBa < ba + ba + b == c + d(a, b)(c, d)

例如。如果两者都genA生成genB素数，那么新生成器应该生成：

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

如果genA和genB是有限列表，压缩然后排序就可以了。

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

这就是我已经走了多远。关于如何以所述方式组合两个生成器的任何想法？

4

1 回答 1

2

如果不保存所有结果，我认为不可能做到这一点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中，当您只对提取集合的最小值感兴趣时，这是一种有效的数据结构。与排序一样，您可以不保存对本身，而是在它们前面加上您要排序的值 ( a+b)，因为元组之间的比较将从比较第一项开始。最后，它将所有元素从堆中弹出，保证其总和小于为下一个生成的任何对的总和，b并产生它们。

请注意，当您生成结果时，两者heap都会saved_a增加，我猜这与到目前为止生成的元素数量的平方根成正比。

使用一些素数进行快速测试：

In [2]: genA = (a for a in [2,3,5,7,11,13,17,19])
In [3]: genB = (b for b in [2,3,5,7,11,13,17,19])
In [4]: for pair in gen_weird_sequence(genA, genB): print pair
(2, 3)
(2, 5)
(3, 5)
(2, 7)
(3, 7)
(5, 7)
(2, 11)
(3, 11)
(2, 13)
(3, 13)
(5, 11)
(5, 13)
(7, 11)
(2, 17)
(3, 17)
(7, 13)

正如预期的那样。使用无限生成器进行测试：

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)]
于 2013-10-18T20:25:43.750 回答