[Python-Dev] Re: PEP 218 (sets); moving set.py to Lib
Guido van Rossum
Wed, 21 Aug 2002 01:23:15 -0400
> 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/)