Generate ordered tuples of infinite sequences

Question

I have two generators genAand genB, and each of them generates an infinite, strictly monotonically increasing sequence of integers.

Now I need a generator that generates all the tuples (a, b), such that it ais created genAand bcreated genBand a < bordered a + bin ascending order. In the case of ambiguity, ordering does not matter, i.e. If a + b == c + d, it does not matter whether it (a, b)first generates or (c, d).

For example. If both genAand genBgenerate prime numbers, the new generator should generate:

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

If genAand genBare the final list, the zipping and then sorting would have done the trick.

Obviously, for all tuples of the form (x, b), the following is true: first(genA) <= x <= max(genA,b) <= bbeing the first(genA)first element generated genAand the max(genA,b)last element generated genA, which is smaller b.

That's how far I got. Any ideas on how to combine the two generators as described?

Answer 1

I do not think that this can be done without saving all the results from genA. The solution might look something like this:

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)]