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