Powersets of a list?

[David C. Ullrich]

On Sat, 26 May 2001 20:09:20 +0200, "Alex Martelli"
<aleaxit at yahoo.com> wrote:

>"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, 

or O(N*2**N) or something like that...

>that IS slow, but how do you
>generate a powerset faster than that?

There have been several power set routines posted.
I suspect that they're all O(N*2^N), but when I time
them (on Windows, starting with a list of length 15)
some of them are at least 10 time faster than
others.

I haven't had any reason to get 2.x so I haven't,
on aint-broke grounds. So I can't compare what
you wrote with, for example, the routine I posted.
Have you compared them? 

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

So _was_ the N*N supposed to be 2**N as
well?

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

The line self.S = N*N in your code. Of course the
self.N = N was supposed to be self.N = len(L),
but it took me a long time to figure out what the
heck the N*N was doing there. I still don't get it -
if those two lines were

self.N = len(L)
self.S = 2**self.N

then I'd see how your routine works, but when
you say self.S = N*N I don't follow it at all.
It's certainly possible that I just don't understand
how the code works. But if you only tested it
on lists of length <= 4 then it's possible that
it doesn't work on longer lists: If N=4 then
N*N = 2**N.

So although I don't see how what you posted
works, I _do_ see how it works for lists
of length 4...

(Since it was actual code, not just a suggestion,
I assumed you'd actually run it. If it was meant as
untested code then never mind. But assuming that
you'd tested it I was puzzled how it could have 
passed the test - then when I saw the example
with a sequence of length 4 that seemed like
a possible explanation.)

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