[Python-Dev] A `cogen' module [was: Re: PEP 218 (sets); moving set.py to Lib]

[Guido van Rossum]

> def cartesian(*sequences):
>     """\
> Generate the `cartesian product' of all SEQUENCES.  Each member of the
> product is a list containing an element taken from each original sequence.
> """
>     if len(sequences) == 0:
> 	yield []
>     else:
> 	first, remainder = sequences[0], sequences[1:]
> 	for element in first:
> 	    for result in cartesian(*remainder):
> 		result.insert(0, element)
> 		yield result

It occurred to me that this is rather ineffecient because it invokes
itself recursively many time (once for each element in the first
sequence).  This version is much faster, because iterating over a
built-in sequence (like a list) is much faster than iterating over a
generator:

def cartesian(*sequences):
    if len(sequences) == 0:
        yield []
    else:
        head, tail = sequences[:-1], sequences[-1]
        for x in cartesian(*head):
            for y in tail:
                    yield x + [y]

I also wonder if perhaps ``tail = list(tail)'' should be inserted
just before the for loop, so that the arguments may be iterators as
well.

I would have more suggestions (I expect that Eric Raymond's powerset
is much faster than your recursive subsets()) but my family is calling
me...

--Guido van Rossum (home page: http://www.python.org/~guido/)