Powersets of a list?
aleaxit at yahoo.com
Sat May 26 20:09:20 CEST 2001
"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
> >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?
More information about the Python-list