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

Tim Peters tim_one@email.msn.com
Wed, 21 Aug 2002 01:11:03 -0400


[Guido, eventually arrives at ...]
> def powerset(base):
>     pairs = list(enumerate(base))
>     size = len(pairs)
>     for n in xrange(2**size):
>         subset = []
>         for e, x in pairs:
>             if n & 2**e:
>                 subset.append(x)
>         yield subset

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]

> 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.

> 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?  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.