On Fri, 2007-07-13 at 17:38 +0000, Jyotirmoy Bhattacharya wrote: > On Jul 13, 6:34 pm, Carsten Haese <[EMAIL PROTECTED]> 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 > > yield subset.union(set([x])) > > > Your recursive_powerset is buggy--it generates too many sets. The loop > over the elements of s is unnecessary. Here is one alternative: > > def recursive_powerset(s): > def do_recursive(S): > if not S: > yield set([]) > return > x=set(S.pop()) > for t in do_recursive(S): > yield t > yield t|x > return do_recursive(s.copy())
Right you are. Note however that x=set(S.pop()) should be x=set([S.pop()]) for this to run. Forget everything I've said about timing comparisons, the correct recursive implementation is actually faster than the iterative implementation I was testing. -Carsten -- http://mail.python.org/mailman/listinfo/python-list
