Fast powerset function

[Evan Klitzke]

On 7/12/07, Evan Klitzke <evan at yelp.com> wrote:
> On 7/12/07, Arash Arfaee <Arash at ece.ucsb.edu> 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 <evan at yelp.com>