Fast powerset function

Antoon Pardon apardon at forel.vub.ac.be
Fri Jul 13 11:16:27 CEST 2007


On 7/12/07, Arash Arfaee <Arash at ece.ucsb.edu> wrote:
> I need a powerset generator function. It's really slow with recursion. Does
> anybody have any idea or code(!!) to do it in an acceptable time?
> Thanks

My idea would be the following.

1) Turn your set into a list: lst

2) let lng be the number of elements.

3) let n range from 0 to 2 ** lng

4) now n represents subset as follows

   consider n as a binary number
   bit k is set in n <=> lst[k] is a member of the subset.

-- 
Antoon Pardon



More information about the Python-list mailing list