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>
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4