6

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([3]), set([1, 2]), set([2]), set([1]), set([])]

as output. How can I achieve this?

linkyndy
  • 17,038
  • 20
  • 114
  • 194
  • 2
    Google for: `python itertools powerset recipe`? That's got exactly what you're asking... and then on http://docs.python.org/2/library/itertools.html - search for `powerset`... – Jon Clements Sep 16 '13 at 11:18
  • It doesn't help me, check the replies below. – linkyndy Sep 16 '13 at 11:36
  • 1
    Well, since the input is a set, then the outputs can't contain duplicates elements, so a tuple makes no odds, convert it back to a set if you really want. Also, since it returns `chain.from_iterable` you in effect have a generator. What is there that you can't easily adapt for whatever your requirement is ? `return imap(set, chain.from_iterable(...))` ? – Jon Clements Sep 16 '13 at 11:41

3 Answers3

18

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 in range(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])
>>>
Pawel Miech
  • 7,742
  • 4
  • 36
  • 57
  • I need to build a generator for this, a function that yields the desired subsets. Also, the generator has to contain sets, not tuples. – linkyndy Sep 16 '13 at 11:35
  • 1
    @Pawelmhm or as per my comment on the OP - just wrap it in an `imap(set, ...)` and keep the function exactly the same... – Jon Clements Sep 16 '13 at 11:47
8

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))
Johannes Charra
  • 29,455
  • 6
  • 42
  • 51
  • I need to build a generator for this, a function that yields the desired subsets. Also, the generator has to contain sets, not tuples. – linkyndy Sep 16 '13 at 11:34
1

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:

def combinations(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 None
        return
    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)]
    while True:
        for i in reversed(range(r)):  # Check from right to left if the index is at its
                                      # max value. If everyone is maxed out, then finish
            if indices[i] != i + n - r:  # indices[2] != 2 + 5 - 3
                break                    # 2 != 4  (Y) then break and avoid the return
        else:
            return
        indices[i] += 1  # indices[2] = 2 + 1 = 3
        for j in range(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]


def all_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 = [[]]

nahuelarjonadev
  • 123
  • 9