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

问题:

Given a set

{0, 1, 2, 3}

What\'s a good way to 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}]

回答1:

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

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.

回答2:

Here is more code for a powerset. This is written from scratch:

>>> def powerset(s):
...     x = len(s)
...     for i in range(1 << x):
...         print [s[j] for j in range(x) if (i & (1 << j))]
...
>>> powerset([4,5,6])
[]
[4]
[5]
[4, 5]
[6]
[4, 6]
[5, 6]
[4, 5, 6]

Mark Rushakoff\'s comment is applicable here: \"If you don\'t like that empty tuple at the beginning, on.\"you can just change the range statement to range(1, len(s)+1) to avoid a 0-length combination\", except in my case you change for i in range(1 << x) to for i in range(1, 1 << x).

---

Returning to this years later, I\'d now write it like this:

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1 << x):
        yield [ss for mask, ss in zip(masks, s) if i & mask]

And then the test code would look like this, say:

print(list(powerset([4, 5, 6])))

Using yield means that you do not need to calculate all results in a single piece of memory. Precalculating the masks outside the main loop is assumed to be a worthwhile optimization.

回答3:

If you\'re looking for a quick answer, I just searched \"python power set\" on google and came up with this: Python Power Set Generator

Here\'s a copy-paste from the code in that page:

def powerset(seq):
    \"\"\"
    Returns all the subsets of this set. This is a generator.
    \"\"\"
    if len(seq) <= 1:
        yield seq
        yield []
    else:
        for item in powerset(seq[1:]):
            yield [seq[0]]+item
            yield item

This can be used like this:

 l = [1, 2, 3, 4]
 r = [x for x in powerset(l)]

Now r is a list of all the elements you wanted, and can be sorted and printed:

r.sort()
print r
[[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]]

回答4:

def powerset(lst):
    return reduce(lambda result, x: result + [subset + [x] for subset in result],
                  lst, [[]])

回答5:

There is a refinement of powerset:

def powerset(seq):
    \"\"\"
    Returns all the subsets of this set. This is a generator.
    \"\"\"
    if len(seq) <= 0:
        yield []
    else:
        for item in powerset(seq[1:]):
            yield [seq[0]]+item
            yield item

回答6:

def get_power_set(s):
  power_set=[[]]
  for elem in s:
    # iterate over the sub sets so far
    for sub_set in power_set:
      # add a new subset consisting of the subset at hand added elem
      power_set=power_set+[list(sub_set)+[elem]]
  return power_set

For example:

get_power_set([1,2,3])

yield

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

回答7:

I just wanted to provide the most comprehensible solution, the anti code-golf version.

from itertools import combinations

l = [\"x\", \"y\", \"z\", ]

def powerset(items):
    combo = []
    for r in range(len(items) + 1):
        #use a list to coerce a actual list from the combinations generator
        combo.append(list(combinations(items,r)))
    return combo

l_powerset = powerset(l)

for i, item in enumerate(l_powerset):
    print \"All sets of length \", i
    print item

---

The results

All sets of length 0

[()]

All sets of length 1

[(\'x\',), (\'y\',), (\'z\',)]

All sets of length 2

[(\'x\', \'y\'), (\'x\', \'z\'), (\'y\', \'z\')]

All sets of length 3

[(\'x\', \'y\', \'z\')]

For more see the itertools docs, also the wikipedia entry on power sets

回答8:

I have found the following algorithm very clear and simple:

def get_powerset(some_list):
    \"\"\"Returns all subsets of size 0 - len(some_list) for some_list\"\"\"
    if len(some_list) == 0:
        return [[]]

    subsets = []
    first_element = some_list[0]
    remaining_list = some_list[1:]
    # Strategy: get all the subsets of remaining_list. For each
    # of those subsets, a full subset list will contain both
    # the original subset as well as a version of the subset
    # that contains first_element
    for partial_subset in get_all_subsets(remaining_list):
        subsets.append(partial_subset)
        subsets.append(partial_subset[:] + [first_element])

    return subsets

Another way one can generate the powerset is by generating all binary numbers that have n bits. As a power set the amount of number with n digits is 2 ^ n. The principle of this algorithm is that an element could be present or not in a subset as a binary digit could be one or zero but not both.

def power_set(items):
    N = len(items)
    # enumerate the 2 ** N possible combinations
    for i in range(2 ** N):
        combo = []
        for j in range(N):
            # test bit jth of integer i
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        yield combo

I found both algorithms when I was taking MITx: 6.00.2x Introduction to Computational Thinking and Data Science, and I consider it is one of the easiest algorithms to understand I have seen.

回答9:

This is wild because none of these answers actually provide the return of an actual Python set. Here is a messy implementation that will give a powerset that actually is a Python set.

test_set = set([\'yo\', \'whatup\', \'money\'])
def powerset( base_set ):
    \"\"\" modified from pydoc\'s itertools recipe shown above\"\"\"
    from itertools import chain, combinations
    base_list = list( base_set )
    combo_list = [ combinations(base_list, r) for r in range(len(base_set)+1) ]

    powerset = set([])
    for ll in combo_list:
        list_of_frozensets = list( map( frozenset, map( list, ll ) ) ) 
        set_of_frozensets = set( list_of_frozensets )
        powerset = powerset.union( set_of_frozensets )

    return powerset

print powerset( test_set )
# >>> set([ frozenset([\'money\',\'whatup\']), frozenset([\'money\',\'whatup\',\'yo\']), 
#        frozenset([\'whatup\']), frozenset([\'whatup\',\'yo\']), frozenset([\'yo\']),
#        frozenset([\'money\',\'yo\']), frozenset([\'money\']), frozenset([]) ])

I\'d love to see a better implementation, though.

回答10:

Here is my quick implementation utilizing combinations but using only built-ins.

def powerSet(array):
    length = str(len(array))
    formatter = \'{:0\' + length + \'b}\'
    combinations = []
    for i in xrange(2**int(length)):
        combinations.append(formatter.format(i))
    sets = set()
    currentSet = []
    for combo in combinations:
        for i,val in enumerate(combo):
            if val==\'1\':
                currentSet.append(array[i])
        sets.add(tuple(sorted(currentSet)))
        currentSet = []
    return sets