Python product of infinite generators

问题:

I'm trying to get the product of 2 infinite generators but the product function in itertools doesn't allow this sort of behaviour.

Example behaviour:

from itertools import *
i = count(1)
j = count(1)
x = product(i, j)

[Killed]

What I want:

x = product(i, j)

((0,0), (0,1), (1,0), (1,1) ...)

It doesn't matter in which order the combinations get returned as long as given infinite time, all combinations will be eventually generated. This means that given a combination of elements, there must be a finite index in the returned generator with that combination.

回答1:

tl;dr

The code presented below is now included in the package infinite on PyPI. So now you can actually just pip install infinite before running this:

from itertools import count
from infinite import product

for x, y in product(count(0), count(0)):
    print(x, y)
    if (x, y) == (3, 3):
        break

---

The lazy solution

If you don't care about order, since the generators are infinite, a valid output would be:

(a0, b1), (a0, b2), (a0, b3), ... (a0, bn), ...

So you can just take the first element from the first generator and then loop over the second.

If you really want to do it, you need a nested loop, and you need to duplicate the nested generator with tee, otherwise you will not be able to loop over it a second time (even if it doesn't matter because you will never exhaust the generator, so you will never need to loop over).

But if you really really really want to do it, here you have it:

from itertools import tee

def product(gen1, gen2):
    for elem1 in gen1:
        gen2, gen2_copy = tee(gen2)
        for elem2 in gen2_copy:
            yield (elem1, elem2)

The idea is to always make a single copy of gen2. Try it with finite generators first.

print(list(product(range(3), range(3,5))))
[(0, 3), (0, 4), (1, 3), (1, 4), (2, 3), (2, 4)]

Then with infinite ones:

print(next(product(count(1), count(1))))
(1, 1)

---

The zig-zag algorithm

As noted by others in comments (and as stated in the previous solution), this will not produce all the combinations. Nevertheless the mapping between natural numbers and pairs of numbers exists, so it must be possible to iterate the pairs in a different way, so that looking for a specific pair (without infinite numbers) can be done in finite time, you need the zig-zag scanning algorithm.

In order to do it you need to cache previous values, so I created a class GenCacher to cache previously extracted values:

class GenCacher:
    def __init__(self, generator):
        self._g = generator
        self._cache = []

    def __getitem__(self, idx):
        while len(self._cache) <= idx:
            self._cache.append(next(self._g))
        return self._cache[idx]

After that you just need to implement the zig-zag algorithm:

def product(gen1, gen2):
    gc1 = GenCacher(gen1)
    gc2 = GenCacher(gen2)
    idx1 = idx2 = 0
    moving_up = True

    while True:
        yield (gc1[idx1], gc2[idx2])

        if moving_up and idx1 == 0:
            idx2 += 1
            moving_up = False
        elif not moving_up and idx2 == 0:
            idx1 += 1
            moving_up = True
        elif moving_up:
            idx1, idx2 = idx1 - 1, idx2 + 1
        else:
            idx1, idx2 = idx1 + 1, idx2 - 1

---

Example

from itertools import count

for x, y in product(count(0), count(0)):
    print(x, y)
    if x == 2 and y == 2:
        break

This produces the following output:

0 0
0 1
1 0
2 0
1 1
0 2
0 3
1 2
2 1
3 0
4 0
3 1
2 2

---

Extend the solution to more than 2 generators

We can edit the solution a bit to make it work even for multiple generators. The basic idea is:

1. iterate over the distance from (0,0) (the sum of the indexes). (0,0) is the only one with distance 0, (1,0) and (0,1) are at distance 1, etc.

2. generate all the tuples of indexes for that distance

3. extract the corresponding element

We still need the GenCacher class, but the code becomes:

def summations(sumTo, n=2):
    if n == 1:
        yield (sumTo,)
    else:
        for head in xrange(sumTo + 1):
            for tail in summations(sumTo - head, n - 1):
                yield (head,) + tail

def product(*gens):
    gens = map(GenCacher, gens)

    for dist in count(0):
        for idxs in summations(dist, len(gens)):
            yield tuple(gen[idx] for gen, idx in zip(gens, idxs))

回答2:

 def product(a, b):
     a, a_copy = itertools.tee(a, 2)
     b, b_copy = itertools.tee(b, 2)
     yield (next(a_copy), next(b_copy))
     size = 1
     while 1:
         next_a = next(a_copy)
         next_b = next(b_copy)
         a, new_a = itertools.tee(a, 2)
         b, new_b = itertools.tee(b, 2)
         yield from ((next(new_a), next_b) for i in range(size))
         yield from ((next_a, next(new_b)) for i in range(size))
         yield (next_a, next_b)
         size += 1

A homebrew solution with itertools.tee. This uses lots of memory as intermediate states are stored in tee

This effectively returns the sides of an ever expanding square:

0 1 4 9 
2 3 5 a
6 7 8 b
c d e f

Given infinite time and infinite memory, this implementation should return all possible products.

回答3:

No matter how you do it, memory will grow a lot, as every value from each iterator will occur an infinite number of times after the first time, so it has to be kept around in some growing variable.

So something like this may work:

def product(i, j):
    """Generate Cartesian product i x j; potentially uses a lot of memory."""
    earlier_values_i = []
    earlier_values_j = []

    # If either of these fails, that sequence is empty, and so is the
    # expected result. So it is correct that StopIteration is raised,
    # no need to do anything.
    next_i = next(i)
    next_j = next(j)
    found_i = found_j = True

    while True:
        if found_i and found_j:
            yield (next_i, next_j)
        elif not found_i and not found_j:
            break  # Both sequences empty

        if found_i: 
            for jj in earlier_values_j:
                yield (next_i, jj)
        if found_j:
            for ii in earlier_values_i:
                yield (ii, next_j)

        if found_i:
            earlier_values_i.append(next_i)
        if found_j:
            earlier_values_j.append(next_j)

        try:
            next_i = next(i)
            found_i = True
        except StopIteration:
            found_i = False

        try:
            next_j = next(j)
            found_j = True
        except StopIteration:
            found_j = False

This was so simple in my head but it looks horribly complicated after typing it out, there must be some simpler way. But I think it will work.

回答4:

You could siply use a generator expresion:

from itertools import *
i = count(1)
j = count(1)

for e in ((x, y) for x in i for y in j):
    yield r

or in python3:

yield from ((x, y) for x in i for y in j)