Powersets of a list?

[Alex Martelli]

"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
news:3b13a688.315231 at nntp.sprynet.com...
    ...
> (The only NxN array of bits that seems at all relevant
> is where the n-th bitmask is all 0's except for a 1 in
> the n-th spot. I don't see how this helps at all with
> __getitem_(self, x) if x is an integer between 0 and
> 2**N - 1. If x is supposed to be a list of N bits then
> I see how the __getitem__ would work, but that's not
> what you meant, is it? If _that's_ what you mean then
> the question would be where we get the list of N bits
> to pass to __getitem__ in the first place...)

The basic idea would be something like:

class PowerSet:
    def __init__(self, L):
        N = len(L)
        self.S = 2**N
        # precompute a couple of things (for speed?)
        self.bits_and_items = [ (1L<<i, L[i]) for i in range(N) ]
    def __getitem__(self, x):
        if x<0: x+=self.S
        if x<0 or x>=self.S: raise IndexError,x
        return [item for bit, item in self.bits_and_items if x&bit]

if __name__=='__main__':
    for x in PowerSet('ciao!'):
        print ''.join(x)

I guess one could play with map and filter rather than
a list comprehension to see if some extra speed is there
to be squeezed out, but that's another issue from the
"precompute for (potential) speed" idea.

Adding this to the timing test does show some small
incremental speed improvements, though nowhere near
enough to make it "competitive":

powerset_Alex( 0.36) 2048:
powerset_AlexClass( 0.44) 2048:
powerset_AlexClassX( 0.28) 2048:
powerset_David( 0.04) 2048:
powerset_Emile( 0.26) 2048:
powerset_Malcolm( 0.05) 2048:
powerset_Walter( 0.08) 2048:
powerset_Alex( 7.06) 32768:
powerset_AlexClass( 8.89) 32768:
powerset_AlexClassX( 6.07) 32768:
powerset_David( 0.87) 32768:
powerset_Emile( 5.46) 32768:
powerset_Malcolm( 1.13) 32768:
powerset_Walter( 1.99) 32768:


The _AlexClassX numbers are for the new version of
the class, the _AlexClass numbers for the old one.


Alex