On 7/12/07, Evan Klitzke <[EMAIL PROTECTED]> wrote: > On 7/12/07, Arash Arfaee <[EMAIL PROTECTED]> wrote: > > I need a powerset generator function. It's really slow with recursion. Does > > anybody have any idea or code(!!) to do it in an acceptable time? > > Thanks > > -Arash > > I thought that this was a really interesting question, so I wrote up a > solution that doesn't use recursion. I didn't test it a whole lot, but > I'm pretty sure it works -- let me know if there are any oversights or > if you can make any improvements ;-) Also, not sure if the line breaks > will be mangled by my mail client, so bear with me if there are any > errors. > > def fact(n): > '''Factorial''' > r = 1 > for i in xrange(1, n + 1): > r *= i > return r > > def nCr(n, r): > '''Number of combinations of r items from n things''' > return fact(n) / (fact(r) * fact(n - r)) > > def get_combinations(slots, tokens): > '''A generator yielding combinations from slots of size tokens''' > maxcombos = nCr(len(slots), tokens) > for index in xrange(maxcombos): > token_copy = tokens > combo = [] > for val in xrange(1, len(slots) + 1): > if not token_copy: > break > thresh = nCr(len(slots) - val, token_copy - 1) > if index < thresh: > combo.append(slots[val-1]) > token_copy -= 1 > else: > index -= thresh > yield tuple(combo) > > def powerset(s): > '''Returns the powerset of s''' > pset = set() > for num_tokens in xrange(1, len(s)): > for combo in get_combinations(s, num_tokens): > pset.add(combo) > # These two are special cases > pset.add(s) > pset.add(tuple()) > return pset > > if __name__ == '__main__': > print powerset((1, 2, 3, 4))
One more obvious thing that I omitted. You can make this a lot faster by caching the values of nCr. This is a simple modification, that I'll leave to the reader ;-) -- Evan Klitzke <[EMAIL PROTECTED]> -- http://mail.python.org/mailman/listinfo/python-list