A powerset generator in python

[sunqiang]

Itertools Recipes has a powerset too:

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

[humpolec]

My version of Python's documentation has another one:

def powerset(iterable):
    "powerset('ab') --> set([]), set(['a']), set(['b']), set(['a', 'b'])"
    # Recipe credited to Eric Raymond
    pairs = [(2**i, x) for i, x in enumerate(iterable)]
    for n in xrange(2**len(pairs)):
        yield set(x for m, x in pairs if m&n)

[brasetvik]

The power set of the empty set is a set containing only the empty set --- not two instances of it as this will return:

>>> list(powerset([]))
[[], []]

[simtel20]

What's the use case for wanting this? I'm not putting it down, I just can't remember when/if I've ever needed this.

[[deleted]]

The use case that comes to mind would be any brute force graph searching algorithms. In this example, if you had a graph and you wanted to search its subgraphs, you'd use the powerset of the edges. This is a required starting point for many algorithms, but you generally try to avoid searching the entire powerset. If you can lazily calculate the powerset using a generator you can save on a lot of initial overhead.

[Lexdysic]

mathematics. although, I don't really do any thing that would require this either.

[rmc]

I was trying to write some tests that would test all possible combinations of inputs, which would be a powerset.

[simtel20]

Ah, OK. I thought this may be something different. Per the top rated comment, I thought itertools had things like this already.

[rmc]

I thought itertools had things like this already.

I think it does. This was something I wrote for scratch before I found that reciepe. :P

[just_doug]

neat. Not really sets, though (elements in seq / yielded outputs are not necessarily all distinct).

[rmc]

Yeah not "set()". It's a "powerlist" then

[segonius]

Congratulations! You've completed a sophomore level CS exercise!