Python: Powerset Of A Given Set With Generators

I am trying to build a list of subsets of a given set in Python with generators. Say I have set([1, 2, 3]) as input, I should have [set([1, 2, 3]), set([2, 3]), set([1, 3]), set

Solution 1:

The fastest way is by using itertools, especially chain and combinations:

>>>from itertools import chain, combinations>>>i = set([1, 2, 3])>>>for z in chain.from_iterable(combinations(i, r) for r inrange(len(i)+1)):
    print z 
()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 3)
(1, 2, 3)
>>>

If you need a generator just use yield and turn tuples into sets:

def powerset_generator(i):
    for subset in chain.from_iterable(combinations(i, r) for r in range(len(i)+1)):
        yield set(subset)

and then simply:

>>> for i in powerset_generator(i):
    print i


set([])
set([1])
set([2])
set([3])
set([1, 2])
set([1, 3])
set([2, 3])
set([1, 2, 3])
>>> 

Solution 2:

From the recipes section of the itertools documentation:

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Solution 3:

I know this is way too old, but I was looking for an answer to the same problem and after a couple hours of non-successful web searching, I came up with my own solution. This is the code:

defcombinations(iterable, r):
    # combinations('ABCDE', 3) --> ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE
    pool = tuple(iterable)  # allows a string to be transformed to a tuple
    n = len(pool)  
    if r > n:  # If we don't have enough items to combine, return Nonereturn
    indices = range(r)  # Make a set of the indices with length (r)yield [pool[i] for i in indices]   Yield first list of indices [0 to (r-1)]
    whileTrue:
        for i inreversed(range(r)):  # Check from right to left if the index is at its# max value. If everyone is maxed out, then finishif indices[i] != i + n - r:  # indices[2] != 2 + 5 - 3break# 2 != 4  (Y) then break and avoid the returnelse:
            return
        indices[i] += 1# indices[2] = 2 + 1 = 3for j inrange(i + 1, r):  # for j in []  # Do nothing in this case
            indices[j] = indices[j - 1] + 1# If necessary, reset indices to the right of# indices[i] to the minimum value possible.# This depends on the current indices[i]yield [pool[i] for i in indices]  # [0, 1, 3]defall_subsets(test):
    out = []
    for i in xrange(len(test)):
        out += [[test[i]]]
    for i in xrange(2, len(test) + 1):
        out += [x for x in combinations(test, i)]
    return out

I took the combinations sample code from itertools doc itertools.combinations and modified it to yield lists instead of tuples. I made annotations when I was trying to figure out how it worked (in order to modify it later), so I'll let them there, just in case someone finds them helpful. Finally, I made all_substes function to find every subset from lengths 1 to r (not including the empty list, so if you need it there just start out as out = [[]]