Fast powerset function

[Evan Klitzke]

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))


-- 
Evan Klitzke <evan at yelp.com>