[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

itertools product(infinite iterator) hangs

On Sat, 14 Sep 2019 at 03:26, Oscar Benjamin <oscar.j.benjamin at gmail.com> wrote:
> I've been staring at this for a little while:
> from itertools import product
> class Naturals:
>     def __iter__(self):
>         i = 1
>         while True:
>             yield i
>             i += 1
> N = Naturals()
> print(iter(N))
> print(product(N))  # <--- hangs
> When I run the above the call to product hangs but I can't see why.

There is already an issue for this:
It seems product always consumes all of its iterators entirely before
yielding anything (in fact before even iter is called). That seemed
surprising to me when looking at the trivial case of a product of one
iterable since in *that* case it is clearly unnecessary.

I wrote my own versions that get around this. This is a simple version:

def iproduct_simple(*iterables):
    '''Returns the Cartesian product of iterables but doesn't hang for
    infinite iterators'''
    if len(iterables) == 0:
        yield ()
    first, others = iterables[0], iterables[1:]
    for f in first:
        for o in iprod(*others):
            yield (f,) + o

This gives output in normal order for finite inputs and doesn't hang
in the case of infinite inputs. However if any of the inputs is
infinite iproduct_simple won't actually yield all elements.

So I made a more complicated version that yields all possibilities
(analogous to enumerating rational numbers):

def iproduct(*iterables):
    '''Returns Cartesian product of iterables. Yields every element
    if len(iterables) == 0:
        yield ()
    elif len(iterables) == 1:
        for e in iterables[0]:
            yield (e,)
    elif len(iterables) == 2:
        for e12 in iproduct2(*iterables):
            yield e12
        first, others = iterables[0], iterables[1:]
        for ef, eo in iproduct2(first, iprod(*others)):
            yield (ef,) + eo

def iproduct2(iterable1, iterable2):
    '''Cartesian product of two possibly infinite iterables'''

    it1 = iter(iterable1)
    it2 = iter(iterable2)

    elems1 = []
    elems2 = []

    sentinel = object()
    def append(it, elems):
        e = next(it, sentinel)
        if e is not sentinel:

    n = 0
    append(it1, elems1)
    append(it2, elems2)

    while n <= len(elems1) + len(elems2):
        for m in range(n-len(elems1)+1, len(elems2)):
            yield (elems1[n-m], elems2[m])
        n += 1
        append(it1, elems1)
        append(it2, elems2)