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

[Eric S. Raymond]

Guido van Rossum <guido@python.org>:
> Here's a generator version:
> 
> def power(s):
>     if len(s) == 0:
>         yield Set()
>     else:
>         # Non-destructively choose a random element:
>         x = Set([iter(s).next()])
>         for ss in power(s - x):
>             yield ss
>             yield ss | x
> 
> I'm not totally happy with this -- it recurses for each element in s,
> creating a new set at each level that is s minus one element.  I'd
> prefer to build the set up from the other end, like the first
> version.

You're right, that is an ugly and opaque piece of code.  Guido me lad,
you have been led down the garden path by a dubious lust for recursive
elegance.  One might almost think you were a LISP hacker or something.

> IOW I'd love to see your version. :-)

Here's the pre-generator version I wrote using lists as the underlying
representation.  Should be trivially transformable into a generator
version.  I'd do it myself but I'm heads-down on bogofilter just now

def powerset(base):
    "Compute the set of all subsets of a set."
    powerset = []
    for n in xrange(2 ** len(base)):
	subset = []
	for e in xrange(len(base)):
	     if n & 2 ** e:
		subset.append(base[e])
	powerset.append(subset)
    return powerset

Are you slapping your forehead yet? :-)
-- 
		<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>