Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

Re: Fast powerset function

 
 
Evan Klitzke
Guest
Posts: n/a
 
      07-13-2007
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:
x.append(s[j])
n >>= 1
result.append(x)

print result


--
Evan Klitzke <(E-Mail Removed)>
 
Reply With Quote
 
 
 
 
Mark Dickinson
Guest
Posts: n/a
 
      07-14-2007
If you don't care about the order of the results, you can use a Gray
code (http://en.wikipedia.org/wiki/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].

Mark


 
Reply With Quote
 
 
 
Reply

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



Advertisments