Fast powerset function
Carsten Haese
carsten at uniqsys.com
Fri Jul 13 15:34:41 CEST 2007
On Fri, 2007-07-13 at 08:15 -0400, I wrote:
> [...]
> def recursive_powerset(s):
> if not s: yield set()
> for x in s:
> s2 = s - set([x])
> for subset in recursive_powerset(s2):
> yield subset
> for subset in recursive_powerset(s2):
> yield subset.union(set([x]))
> [...]
Pardon the soliloquy, but now that I'm a bit more awake, I realize that
this is unnecessarily slow due to the duplicate invocation of the
recursive call. Changing it thusly cuts the run time roughly in half:
def recursive_powerset(s):
if not s: yield set()
for x in s:
s2 = s - set([x])
for subset in recursive_powerset(s2):
yield subset
yield subset.union(set([x]))
However, this doesn't change the fact that the iterative method blows
the recursive method out of the water.
--
Carsten Haese
http://informixdb.sourceforge.net
More information about the Python-list
mailing list