Velocity Reviews > Re: Fast powerset function

# 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)>

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