[Python-Dev] Re: PEP 218 (sets); moving set.py to Lib

[Guido van Rossum]

> Now let's rewrite that in modern Python <wink>:
> 
> def powerset(base):
>     pairs = [(2**i, x) for i, x in enumerate(base)]
>     for i in xrange(2**len(pairs)):
>         yield [x for (mask, x) in pairs if i & mask]

Honest, I didn't see this before I posted mine. :-)

> > This is a generator that yields a series of lists whose values are the
> > items of base.  And again, like cartesian product, it's now more a
> > generator thing than a set thing.
> 
> Generators are great for constructing families of combinatorial
> objects, BTW.  They can be huge, and in algorithms that use them as
> inputs for searches, you can often expect not to need more than a
> miniscule fraction of the entire family, but can't predict how many
> you'll need.  Generators are perfect then.

Yup.  That's why I strove for these to be generators.

> > BTW, the correctness of all my versions trivially derives from the
> > correctness of your version -- each is a very simple
> > transformation of the previous one.  My mentor Lambert Meertens
> > calls this process Algorithmics (and has developed a mathematical
> > notation and theory for program transformations).
> 
> Was he interested in that before his sabbatical with the SETL folks?

Dunno.  Maybe it sparked his interest.

> The SETL project produced lots of great research in that area,
> largely driven by the desire to help ultra-high-level SETL programs
> finish in their lifetimes.

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