Powersets of a list?

[Alex Martelli]

"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
news:3b0fabc2.5506652 at nntp.sprynet.com...
> On Fri, 25 May 2001 18:19:10 +0200, "Alex Martelli"
> <aleaxit at yahoo.com> wrote:
>
> >"Emile van Sebille" <emile at fenx.com> wrote in message
> >news:9els3j$2kap$1 at ID-11957.news.dfncis.de...
> >> This seems to do it:
> >    [znip]
> >> > I was wondering if, given a list  [1,2,3], one can generate its power
> >set?
> >
> >What about a concise form such as...:
> >
> >def powerset(L):
> >    N = len(L)
> >    return [ [L[i] for i in range(N) if X&(1L<<i)]
> >        for X in range(2**N) ]
>
> In a lower-level language where sets are implemented
> as patterns of bits then the thing corresponding to
> range(2**N) _is_ the power set.  But here surely
> all that shifting, etc, makes this extremely slow?

I dunno, slow compared to what?  It's going to be
O(2**N) of course, that IS slow, but how do you
generate a powerset faster than that?

> (Could be I finally have to give in and get 2.x
> to find out.)
>
> >or, to avoid consuming too much memory, a class
> >whose instances 'are' sequences of L's subsets
> >might be quite appropriate here:
> >
> >class Powerset:
> >    def __init__(self, L):
> >        self.L = L
> >        self.N = N
> >        self.S = N*N
> >    def __getitem__(self, x):
> >        if x<0: x+=self.S
> >        if x<0 or x>=self.S: raise IndexError,x
> >        return [self.L[i] for i in range(self.N)
> >            if x&(1L<<i)]
>
> ??? Presumably the string "N" is a reserved
> word in 2.x, with magic properties so that
> self.N = N becomes self.N=len(L) and
> self.S=N*N becomes self.S=2**self.N?

Naah, I obviously just forgot to copy the line
    N = len(L)
over from the previously quoted function
powerset to the first or second line of this
Powerset class's __init__ method.  Trivial.


> >I haven't supported slicing in this example, but
> >it wouldn't be terribly hard.  Anyway, it lets
> >you do such typical tasks as:
> >
> >    for sq in Powerset('ciao'):
> >        print ''.join(sq)
>
> (Or maybe the fact that 4*4 = 2**4 has something
> to do with it...)

To do with what?


Alex