> 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? :-)
Yes! I didn't actually know that algorithm.
Here's the generator version for sets (still requires a real set as
input):
def powerset(base):
size = len(base)
for n in xrange(2**size):
subset = []
for e, x in enumerate(base):
if n & 2**e:
subset.append(x)
yield Set(subset)
I would like to write n & (1<<e) instead of n & 2**e; but 1<<e drops
bits when e is > 31. Now, for a set with that many elements, there's
no hope that this will ever complete in finite time, but does that
mean it shouldn't start? I could write 1L<<e and avoid the issue, but
then I'd be paying for long ops that I'll only ever need in a case
that's only of theoretical importance.
A variation: rather than calling enumerate(base) 2**size times,
concretize in it into a list. We know it can't be very big or else
the result isn't representable:
def powerset(base):
size = len(base)
pairs = list(enumerate(base))
for n in xrange(2**size):
subset = []
for e, x in pairs:
if n & 2**e:
subset.append(x)
yield Set(subset)
Ah, and now it's trivial to write this so that base can be an
arbitrary iterable again, rather than a set (or sequence):
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
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.
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).
Thanks!
--Guido van Rossum (home page: http://www.python.org/~guido/)
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