Powersets of a list?

[David C. Ullrich]

On Sun, 27 May 2001 19:11:09 +0200, "Alex Martelli"
<aleaxit at yahoo.com> wrote:

>"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
>news:3b11015c.2099508 at nntp.sprynet.com...
>    ...
>> 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.
>
>Yes, the multiplicative constants are indeed widely
>different.
>
>> 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?
>
>I had not measured performance, no -- just 'compared'
>them in terms of compactness of source code.
>
>
>> So although I don't see how what you posted
>> works, I _do_ see how it works for lists
>
>You're right, it didn't work (not even for lists
>of length 4, since I had forgotten to compute N).

Yeah, the reason I figured your test might have
worked anyway is I figured maybe there was
an "N=4" somewhere above...

>As an apology, here's the performance measurement
>you requested.  First, the code -- all the versions of
>powersets that were posted so far, with minimal
>renaming (it seems there actually were no conflicts,
>due to different usage of upper/lower case).
>
>import time
[...]
>powerset_Alex( 0.75) 2048:
>powerset_AlexClass( 0.63) 2048:
>powerset_David( 0.06) 2048:
>powerset_Emile( 0.37) 2048:
>powerset_Malcolm( 0.08) 2048:
>powerset_Walter( 0.14) 2048:
>powerset_Alex(11.48) 32768:
>powerset_AlexClass(12.94) 32768:
>powerset_David( 2.00) 32768:
>powerset_Emile( 7.37) 32768:
>powerset_Malcolm( 2.49) 32768:
>powerset_Walter( 3.49) 32768:

The funny thing about this is that when I offered
mine I said I imagined it was probably the slowest
possible solution - wasn't being ironic, I figured
it probably was. I was wrong.

I think that comparing AlexClass with the others
is like testing the relative speed of range()
versus xrange(); of course xrange will be faster
because it hasn't actually constructed the entire
list in the sense that range has. (And of course
the AlexClass version is the one you'd want in some
situations, for just that reason.)

>As a side effect, this does show the same powersets, net of order,
>are being returned.
>
>
>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)