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
--
http://mail.python.org/mailman/listinfo/python-list
