How to get all subsets of a set? (powerset)

python set powerset
patrick picture patrick · Sep 27, 2009 · Viewed 99.5k times · Source

Given a set 

{0, 1, 2, 3}

How can I produce the subsets:

[set(),
 {0},
 {1},
 {2},
 {3},
 {0, 1},
 {0, 2},
 {0, 3},
 {1, 2},
 {1, 3},
 {2, 3},
 {0, 1, 2},
 {0, 1, 3},
 {0, 2, 3},
 {1, 2, 3},
 {0, 1, 2, 3}]

Answer

Mark Rushakoff picture Mark Rushakoff · Sep 27, 2009

The Python itertools page has exactly a powerset recipe for this:

from itertools import chain, combinations

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

Output:

>>> list(powerset("abcd"))
[(), ('a',), ('b',), ('c',), ('d',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')]

If you don't like that empty tuple at the beginning, you can just change the range statement to range(1, len(s)+1) to avoid a 0-length combination.

Related questions

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([3]), set([1, 2]), set([2]), set([1]), set([])] as output. How can I achieve …

Read More
Get difference between two lists

I have two lists in Python, like these: temp1 = ['One', 'Two', 'Three', 'Four'] temp2 = ['One', 'Two'] I need to create a third list with items from the first list which aren't present in the second one. From the example I …

Read More
Append values to a set in Python

I have a set like this: keep = set(generic_drugs_mapping[drug] for drug in drug_input) How do I add values [0,1,2,3,4,5,6,7,8,9,10] into this set?

Read More