Powersets of a list?

[David C. Ullrich]

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?
(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?

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

>Alex
>
>
>



David C. Ullrich
*********************
"Sometimes you can have access violations all the 
time and the program still works." (Michael Caracena, 
comp.lang.pascal.delphi.misc 5/1/01)