Fast powerset function
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?
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.
More information about the Python-list