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

**Eric S. Raymond
**
esr@thyrsus.com

*Tue, 20 Aug 2002 22:57:25 -0400*

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>