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))
--
Evan Klitzke <[EMAIL PROTECTED]>
--
http://mail.python.org/mailman/listinfo/python-list
