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

find all subsets of a set using recursion python
all subsets of a set python
power set python recursion
find all subsets of an array in c
powerset python
write a python class to get all possible unique subsets from a set of distinct integers
given a set of distinct integers, nums, return all possible subsets (the power set).
power set algorithm

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}]

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.

Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, Get the size of power set powet_set_size = pow(2, set_size) 2 Loop for  To calculate a powerset P of a set s with n elements, simply calculate the powerset P’ of a subset of s with (n-1) elements and add the n-th element to each set in the powerset P’. Now merge the resulting set of sets with the previous powerset P’ and you get the powerset P. In other words, start with the empty set {} and put it into a temporary set of sets P’. Now go over all elements x in s.


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.

explore(recursion) and make start = i+1 to go through remaining elements of the array. Remove element from the list. Here is java code for  A Power Set is a set of all the subsets of a set. Maybe an example will help And these are also subsets: {a,b}, {a,c} and {b,c} And altogether we get the Power Set of {a,b,c}: Think of it as all the different ways we can select the items (the order of the items doesn't matter), including selecting none, or all.


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

All of the resulting sets make up the power set for [1, 2, 3]. Code. JavaScript, Python. function powerSet(arr) { // the final power  You can find all subsets of set or power set using recursion. Here is the simple approach. As each recursion call will represent subset here, we will add resultList (see recursion code below) to the list of subsets in each call. Iterate over elements of a set. In each iteration.


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

Power Set. A Power Set is a set of all the subsets of a set. OK? Got that? Maybe an example a subset of {a,b,c}. And altogether we get the Power Set of {a,b,c}:. Recursive program to generate power set Given a set represented as string, write a recursive code to print all subsets of it. The subsets can be printed in any order.


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

If you want to calculate a set containing all subsets of set (also called power set) you could either choose an recursive approach or try this  Input: Set [], set_size 1. Get the size of power set powet_set_size = pow (2, set_size) 2 Loop for counter from 0 to pow_set_size (a) Loop for i = 0 to set_size (i) If ith bit in counter is set Print ith element from set for this subset (b) Print separator for subsets i.e., newline.


The power set of a given set S is the set of all subsets of S, including S Thus, we can easily use it to get the power set of the given set, too: ? Given a set of positive integers, find all its subsets. The set can contain duplicate elements, so any repeated subset should be considered only once in the output. The idea is to use a bit-mask pattern to generate all the combinations as discussed in previous post. But previous post will print duplicate subsets if the elements are repeated in


Print power set of any given set OR Print all subsets of a set OR Collect empty subset ([ ]) first because empty subset will be subset of any set  Starting from right, 1 at ith position shows that the ith element of the set is present as 0 shows that the element is absent. Therefore, what we have to do is just generate the binary numbers from 0 to 2^n – 1, where n is the length of the set or the numbers of elements in the set. // A Java program to print all subsets of a set.


Given a set S, generate all distinct subsets of it i.e., find distinct power set of set S. A power set of any set S is the set of all subsets of S, including the empty set  For n>1, find the set of subsets of 1,,n-1 and make two copies of it. For one of them, add n to each subset. Then take the union of the two copies. Edit To make it crystal clear: The set of subsets of {1} is {{}, {1}} For {1, 2}, take {{}, {1}}, add 2 to each subset to get {{2}, {1, 2}} and take the union with {{}, {1}} to get {{}, {1}, {2}, {1, 2}}