Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Re: Fast powerset function

Thread Tools

Re: Fast powerset function

Evan Klitzke
Posts: n/a
On 7/12/07, Arash Arfaee <(E-Mail Removed)> 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
> -Arash

Here's a much simpler (and faster) solution I got from a coworker:

s = range(1
result = []

l = len(s)
for i in range(2**l):
n = i
x = []
for j in range(l):
if n & 1:
n >>= 1

print result

Evan Klitzke <(E-Mail Removed)>
Reply With Quote
Mark Dickinson
Posts: n/a
If you don't care about the order of the results, you can use a Gray
code ( this has the advantage
of only adding or removing a single element to get from one subset to
the next.

def powerset(s):
d = dict(zip(
(1<<i for i in range(len(s))),
(set([e]) for e in s)

subset = set()
yield subset
for i in range(1, 1<<len(s)):
subset = subset ^ d[i & -i]
yield subset

>>> list(powerset('abc'))

[set([]), set(['a']), set(['a', 'b']), set(['b']), set(['c', 'b']),
set(['a', 'c', 'b']), set(['a', 'c']), set(['c'])]

If you're using the subsets as they appear and don't need to store
them all at once, then it's significantly faster (on my machine) if
you replace the line subset = subset ^ d[i & -i] with an in-place
update: subset ^= d[i & -i].


Reply With Quote

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Fast powerset function Evan Klitzke Python 6 07-13-2007 05:56 PM
Re: Fast powerset function Evan Klitzke Python 0 07-13-2007 06:53 AM
powerset Gunnar G C++ 1 08-09-2005 11:46 AM
powerset operation matt Perl 0 01-17-2004 06:50 AM
Powerset Tim Rowe Python 0 09-15-2003 06:41 PM