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

Question

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

Eliathas

@X10D many. For instance: scholar.google.com/… – Chitter

@X10D For constraint based causal discovery algorithms one needs to test conditional independence by conditioning on all possible subsets of the variables involved, I have also come across needing the powerset when computing the Fourier series for Boolean functions. This is obviously the tip of the iceberg – Dearing

@X10D Asking what are the applications of a power set is a bit like asking what are the applications of subsets. It is a fundamental mathematical concept. What to use it for is up to you. I have used it for trying various combinations of things. Suppose your set contains actions and you want to test all possible subsets of actions. Iterating over the power set then feels natural. – Hodgkin

Answer 1

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.

Apodaca

This is the fastest answer I could find, comparing some other solutions on this page to this one using Python's timeit module. However, in certain cases, if you need to modify the resulting output (e.g. joining the letters to form strings) writing a custom recipe utilizing generators and building up the output you want (e.g. adding together two strings) can be much faster. – Eiffel

why is s = list(iterable) needed? – Baziotes

@JackStevens because iterables are not rewindable and are not required to have __len__ implemented; try out powerset((n for n in range(3))) without the list wrapping. – Veron

for large strings, this would eat lot of memory! – Patchouli

@AlexandreHuat: Ranges are lazy sequences, not iterators. powerset(range(3)) would work fine even without s = list(iterable). – Ancheta

Ceasar Bautista - did you try timing my solution? My tests just now seem to indicate that mine is over 2.5x faster. gist.github.com/ciphergoth/22569ed316a61e40f7ef49f986e9704f – Habitue

Answer 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.

Brittenybrittingham

This is a creative answer. However, I measured it using timeit to compare it to Mark Rushakoff and noticed it was significantly slower. To generate the power set of 16 items 100 times, my measurements were 0.55 versus 15.6. – Eiffel

how do you handle duplicates? – Greenstein

Any problem of duplicates in python can be solved using set(). – Drennen

@CeasarBautista you can't compare a user function with a built in function. Built in Functions are always optimized whereever possible – Edam

@Edam what do you mean by "you can't compare"? If you don't compare them, how do you decide which one to choose? – Chitter

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

Norma

In case of an empty array as input, the above code would return [[][]], to fix that just separate the cases for length checking if len(seq) == 0: yield [] elif len(seq) == 1: yield seq yield [] – Galway

For reference, I measured this (with Ayush's edit) using timeit and compared it to the powerset recipe in Mark Rushakoff's answer. On my machine, to generate the powerset of 16 items 100 times, this algorithm took 1.36 seconds while Rushakoff's took 0.55. – Eiffel

What will be the time complexity for this? – Libradalibrarian

@Libradalibrarian I evaluated time complexity of copy-paste section. For me, it feels like O(n^2). The for loop contributes 1 n, recursive call contributes n-1. So, in total it becomes O(n^2). Along with these, if we consider outside loop that calls powerset(l), another n is multiplied with the previous result, making it O(n^3). I am a beginner and student in this. So please do correct me if my perspective is wrong. Stay safe. – Tonedeaf

Answer 4

Use function powerset() from package more-itertools.

Yields all possible subsets of the iterable

>>> list(powerset([1, 2, 3]))
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

If you want sets, use:

list(map(set, powerset(iterable)))

Chitter

So many people reinventing the wheel here, IMHO this is the best answer as it may already be in your dependencies since it's required by many common libraries, e.g. pytest. libraries.io/pypi/more-itertools/dependents – Capercaillie

It's not always the right choice to introduce a dependency for a three-liner. – Habitue

1) A three-liner? Are you referencing to the implementation given in itertools? 2) Is such a light package a problematic dependency? – Chitter

Answer 5

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

Generation

you should add from functools import reduce – Gianna

Answer 6

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_powerset(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.

Hyalite

Answer 7

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

Thermogenesis

Answer 8

TL;DR (go directly to Simplification)

I know I have previously added an answer, but I really like my new implementation. I am taking a set as input, but it actually could be any iterable, and I am returning a set of sets which is the power set of the input. I like this approach because it is more aligned with the mathematical definition of power set (set of all subsets).

def power_set(A):
    """A is an iterable (list, tuple, set, str, etc)
    returns a set which is the power set of A."""
    length = len(A)
    l = [a for a in A]
    ps = set()

    for i in range(2 ** length):
        selector = f'{i:0{length}b}'
        subset = {l[j] for j, bit in enumerate(selector) if bit == '1'}
        ps.add(frozenset(subset))

    return ps

If you want exactly the output you posted in your answer use this:

>>> [set(s) for s in power_set({1, 2, 3, 4})]
[{3, 4},
 {2},
 {1, 4},
 {2, 3, 4},
 {2, 3},
 {1, 2, 4},
 {1, 2},
 {1, 2, 3},
 {3},
 {2, 4},
 {1},
 {1, 2, 3, 4},
 set(),
 {1, 3},
 {1, 3, 4},
 {4}]

Explanation

It is known that the number of elements of the power set is 2 ** len(A), so that could clearly be seen in the for loop.

I need to convert the input (ideally a set) into a list because by a set is a data structure of unique unordered elements, and the order will be crucial to generate the subsets.

selector is key in this algorithm. Note that selector has the same length as the input set, and to make this possible it is using an f-string with padding. Basically, this allows me to select the elements that will be added to each subset during each iteration. Let's say the input set has 3 elements {0, 1, 2}, so selector will take values between 0 and 7 (inclusive), which in binary are:

000 # 0
001 # 1
010 # 2
011 # 3
100 # 4
101 # 5
110 # 6
111 # 7

So, each bit could serve as an indicator if an element of the original set should be added or not. Look at the binary numbers, and just think of each number as an element of the super set in which 1 means that an element at index j should be added, and 0 means that this element should not be added.

I am using a set comprehension to generate a subset at each iteration, and I convert this subset into a frozenset so I can add it to ps (power set). Otherwise, I won't be able to add it because a set in Python consists only of immutable objects.

Simplification

You can simplify the code using some python comprehensions, so you can get rid of those for loops. You can also use zip to avoid using j index and the code will end up as the following:

def power_set(A):
    length = len(A)
    return {
        frozenset({e for e, b in zip(A, f'{i:{length}b}') if b == '1'})
        for i in range(2 ** length)
    }

That's it. What I like of this algorithm is that is clearer and more intuitive than others because it looks quite magical to rely on itertools even though it works as expected.

Hyalite

This is basically the same idea as in this previous answer https://mcmap.net/q/126538/-how-to-get-all-subsets-of-a-set-powerset-duplicate – Sarraceniaceous

Answer 9

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 to it
      # effectively doubling the sets resulting in the 2^n sets in the powerset of s.
      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]]

Stratocumulus

Modifying a loop variable (power_set) in the loop that it governs is a very questionable practice. For example, suppose you wrote this instead of the proposed variable-modifying code: power_set += [list(sub_set)+[elem]]. Then the loop does not terminate. – Brittenybrittingham

Answer 10

This can be done very naturally with itertools.product:

import itertools

def powerset(l):
    for sl in itertools.product(*[[[], [i]] for i in l]):
        yield {j for i in sl for j in i}

Habitue

most elegant answer given to this question – Pathology

@ArthurB. https://mcmap.net/q/126538/-how-to-get-all-subsets-of-a-set-powerset-duplicate – Chitter

Not only the most elegant but also the fastest by quite a big margin, it seems gist.github.com/ciphergoth/22569ed316a61e40f7ef49f986e9704f (search this thread for "timeit") – Habitue

Answer 11

I know this is too late

There are many other solutions already but still...

def power_set(lst):
    pw_set = [[]]

    for i in range(0,len(lst)):
        for j in range(0,len(pw_set)):
            ele = pw_set[j].copy()
            ele = ele + [lst[i]]
            pw_set = pw_set + [ele]

    return pw_set

Carranza

Answer 12

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

Odontograph

Answer 13

With empty set, which is part of all the subsets, you could use:

def subsets(iterable):
    for n in range(len(iterable) + 1):
        yield from combinations(iterable, n)

Becoming

Answer 14

from itertools import combinations
def subsets(arr: set) -> list:
   subsets = []
   [subsets.extend(list(combinations(arr,n))) for n in range(len(arr))]
   return subsets 

a = {1,2,3}
print(subsets(a))

Output:

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

For sorted subsets, we can do:

# sorted subsets
print(sorted(subsets(a)))

Output:

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

Estabrook

Answer 15

def powerSet(s):
    sets = [[]]
    for i in s:
        newsets = []
        for k in sets:
            newsets.append(k+[i])
        sets += newsets
    return sets

Code first, for those who want a simple answer. I have a good explanation here https://leetcode.com/problems/subsets/solutions/3138042/simple-python-solution/

But the short answer is that you start with the set of the empty set, i.e. "sets = [[]]". I recommend to put a print a statement under "for i in s" i.e. "print(sets)" and see that it doubles for each element i

Farandole

+1 since this is the first implementation that doesn't require len(s) and can stream its answers without materializing the whole list up front. It also builds the combinations in a way that only pulls new items from s after all combinations of previous answers are generated -- also good for streaming! And, not recursive! Only change needed is to add "yield from newsets" after "sets += newsets" (at the same indent) and get rid of "return sets" at the end – Corticosterone

this code doesn't generate the empty set. easy to fix by adding a "yield sets" after setting sets (that is between line 2 and 3) I really like that this is a generator – Capitular

Answer 16

Just a quick power set refresher !

Power set of a set X, is simply the set of all subsets of X including the empty set

Example set X = (a,b,c)

Power Set = { { a , b , c } , { a , b } , { a , c } , { b , c } , { a } , { b } , { c } , { } }

Here is another way of finding power set:

def power_set(input):
    # returns a list of all subsets of the list a
    if (len(input) == 0):
        return [[]]
    else:
        main_subset = [ ]
        for small_subset in power_set(input[1:]):
            main_subset += [small_subset]
            main_subset += [[input[0]] + small_subset]
        return main_subset

print(power_set([0,1,2,3]))

full credit to source

Arabele

Answer 17

If you want any specific length of subsets you can do it like this:

from itertools import combinations
someSet = {0, 1, 2, 3}
([x for i in range(len(someSet)+1) for x in combinations(someSet,i)])

More generally for arbitary length subsets you can modify the range arugment. The output is

[(), (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)]

Wiencke

Answer 18

You can do it like this:

def powerset(x):
    m=[]
    if not x:
        m.append(x)
    else:
        A = x[0]
        B = x[1:]
        for z in powerset(B):
            m.append(z)
            r = [A] + z
            m.append(r)
    return m

print(powerset([1, 2, 3, 4]))

Output:

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

Angelicaangelico

Might I suggest that when posting a code solution, be kind enough to give a detailed explanation of what the code is doing and why you use this or that method to solve a problem. New coders should not just look at a code block and copy/paste it without knowing exactly what the code is doing and why. Thanks and welcome to Stackoverflow. – Corset

A really impressive and recursive answer. – Allurement

Answer 19

A simple way would be to harness the internal representation of integers under 2's complement arithmetic.

Binary representation of integers is as {000, 001, 010, 011, 100, 101, 110, 111} for numbers ranging from 0 to 7. For an integer counter value, considering 1 as inclusion of corresponding element in collection and '0' as exclusion we can generate subsets based on the counting sequence. Numbers have to be generated from 0 to pow(2,n) -1 where n is the length of array i.e. number of bits in binary representation.

A simple Subset Generator Function based on it can be written as below. It basically relies

def subsets(array):
    if not array:
        return
    else:
        length = len(array)
        for max_int in range(0x1 << length):
            subset = []
            for i in range(length):
                if max_int & (0x1 << i):
                    subset.append(array[i])
            yield subset

and then it can be used as

def get_subsets(array):
    powerset = []
    for i in subsets(array):
        powerser.append(i)
    return powerset

Testing

Adding following in local file

if __name__ == '__main__':
    sample = ['b',  'd',  'f']

    for i in range(len(sample)):
        print "Subsets for " , sample[i:], " are ", get_subsets(sample[i:])

gives following output

Subsets for  ['b', 'd', 'f']  are  [[], ['b'], ['d'], ['b', 'd'], ['f'], ['b', 'f'], ['d', 'f'], ['b', 'd', 'f']]
Subsets for  ['d', 'f']  are  [[], ['d'], ['f'], ['d', 'f']]
Subsets for  ['f']  are  [[], ['f']]

Hassiehassin

This may not be practical regarding maintainability or readability, but it blew my mind. Thanks for sharing, smart solution! – Capercaillie

Answer 20

Almost all of these answers use list rather than set, which felt like a bit of a cheat to me. So, out of curiosity I tried to do a simple version truly on set and summarize for other "new to Python" folks.

I found there's a couple oddities in dealing with Python's set implementation. The main surprise to me was handling empty sets. This is in contrast to Ruby's Set implementation, where I can simply do Set[Set[]] and get a Set containing one empty Set, so I found it initially a little confusing.

To review, in doing powerset with sets, I encountered two problems:

1. set() takes an iterable, so set(set()) will return set() because the empty set iterable is empty (duh I guess :))
2. to get a set of sets, set({set()}) and set.add(set) won't work because set() isn't hashable

To solve both issues, I made use of frozenset(), which means I don't quite get what I want (type is literally set), but makes use of the overall set interace.

def powerset(original_set):
  # below gives us a set with one empty set in it
  ps = set({frozenset()}) 
  for member in original_set:
    subset = set()
    for m in ps:
      # to be added into subset, needs to be
      # frozenset.union(set) so it's hashable
      subset.add(m.union(set([member]))
    ps = ps.union(subset)
  return ps

Below we get 2² (16) frozensets correctly as output:

In [1]: powerset(set([1,2,3,4]))
Out[2]:
{frozenset(),
 frozenset({3, 4}),
 frozenset({2}),
 frozenset({1, 4}),
 frozenset({3}),
 frozenset({2, 3}),
 frozenset({2, 3, 4}),
 frozenset({1, 2}),
 frozenset({2, 4}),
 frozenset({1}),
 frozenset({1, 2, 4}),
 frozenset({1, 3}),
 frozenset({1, 2, 3}),
 frozenset({4}),
 frozenset({1, 3, 4}),
 frozenset({1, 2, 3, 4})}

As there's no way to have a set of sets in Python, if you want to turn these frozensets into sets, you'll have to map them back into a list (list(map(set, powerset(set([1,2,3,4])))) ) or modify the above.

Levitt

Answer 21

Perhaps the question is getting old, but I hope my code will help someone.

def powSet(set):
    if len(set) == 0:
       return [[]]
    return addtoAll(set[0],powSet(set[1:])) + powSet(set[1:])

def addtoAll(e, set):
   for c in set:
       c.append(e)
   return set

Pederast

ew, recursion! =) – Monacid

Probably not the most efficient way, but it is always interesting to see the recursive way! – Pederast

Answer 22

Getting all the subsets with recursion. Crazy-ass one-liner

from typing import List

def subsets(xs: list) -> List[list]:
    return subsets(xs[1:]) + [x + [xs[0]] for x in subsets(xs[1:])] if xs else [[]]

Based on a Haskell solution

subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = map (x:) (subsets xs) ++ subsets xs

Meson

NameError: name 'List' is not defined – Vedette

@Vedette I've added List import – Cornetist

Answer 23

def findsubsets(s, n): 
    return list(itertools.combinations(s, n)) 

def allsubsets(s) :
    a = []
    for x in range(1,len(s)+1):
        a.append(map(set,findsubsets(s,x)))      
    return a

Karelia

Code-only answers are considered low quality: make sure to provide an explanation what your code does and how it solves the problem. It will help the asker and future readers both if you can add more information in your post. See Explaining entirely code-based answers – Theomancy

Answer 24

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.

Stralka

Good point, but the OP wants a list of sets as the output, so (in Python 3) you can do [*map(set, chain.from_iterable(combinations(s, r) for r in range(len(s)+1)))]; the function arg of map can be frozenset if you prefer. – Jeana

Answer 25

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

Rositaroskes

Answer 26

All subsets in range n as set:

n = int(input())
l = [i for i in range (1, n + 1)]

for number in range(2 ** n) :
    binary = bin(number)[: 1 : -1]
    subset = [l[i] for i in range(len(binary)) if binary[i] == "1"]
    print(set(sorted(subset)) if number > 0 else "{}")

Sligo

Answer 27

import math    
def printPowerSet(set,set_size): 
    pow_set_size =int(math.pow(2, set_size))
    for counter in range(pow_set_size):
    for j in range(set_size):  
        if((counter & (1 << j)) > 0):
            print(set[j], end = "")
    print("")
set = ['a', 'b', 'c']
printPowerSet(set,3)

Sela

Answer 28

A variation of the question, is an exercise I see on the book "Discovering Computer Science: Interdisciplinary Problems, Principles, and Python Programming. 2015 edition". In that exercise 10.2.11, the input is just an integer number, and the output should be the power sets. Here is my recursive solution (not using anything else but basic python3 )

def powerSetR(n):
    assert n >= 0
    if n == 0:
        return [[]]
    else:
        input_set = list(range(1, n+1)) # [1,2,...n]
        main_subset = [ ]
        for small_subset in powerSetR(n-1):
            main_subset += [small_subset]
            main_subset += [ [input_set[-1]] + small_subset]
        return main_subset

superset = powerSetR(4)
print(superset)       
print("Number of sublists:", len(superset))

And the output is

[[], [4], [3], [4, 3], [2], [4, 2], [3, 2], [4, 3, 2], [1], [4, 1], [3, 1], [4, 3, 1], [2, 1], [4, 2, 1], [3, 2, 1], [4, 3, 2, 1]] Number of sublists: 16

Nena

Answer 29

I hadn't come across the more_itertools.powerset function and would recommend using that. I also recommend not using the default ordering of the output from itertools.combinations, often instead you want to minimise the distance between the positions and sort the subsets of items with shorter distance between them above/before the items with larger distance between them.

The itertools recipes page shows it uses chain.from_iterable

• Note that the r here matches the standard notation for the lower part of a binomial coefficient, the s is usually referred to as n in mathematics texts and on calculators (“n Choose r”)

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

The other examples here give the powerset of [1,2,3,4] in such a way that the 2-tuples are listed in "lexicographic" order (when we print the numbers as integers). If I write the distance between the numbers alongside it (i.e. the difference), it shows my point:

12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1

The correct order for subsets should be the order which 'exhausts' the minimal distance first, like so:

12 ⇒ 1
23 ⇒ 1
34 ⇒ 1
13 ⇒ 2
24 ⇒ 2
14 ⇒ 3

Using numbers here makes this ordering look 'wrong', but consider for example the letters ["a","b","c","d"] it is clearer why this might be useful to obtain the powerset in this order:

ab ⇒ 1
bc ⇒ 1
cd ⇒ 1
ac ⇒ 2
bd ⇒ 2
ad ⇒ 3

This effect is more pronounced with more items, and for my purposes it makes the difference between being able to describe the ranges of the indexes of the powerset meaningfully.

(There is a lot written on Gray codes etc. for the output order of algorithms in combinatorics, I don't see it as a side issue).

I actually just wrote a fairly involved program which used this fast integer partition code to output the values in the proper order, but then I discovered more_itertools.powerset and for most uses it's probably fine to just use that function like so:

from more_itertools import powerset
from numpy import ediff1d

def ps_sorter(tup):
    l = len(tup)
    d = ediff1d(tup).tolist()
    return l, d

ps = powerset([1,2,3,4])

ps = sorted(ps, key=ps_sorter)

for x in ps:
    print(x)

⇣

()
(1,)
(2,)
(3,)
(4,)
(1, 2)
(2, 3)
(3, 4)
(1, 3)
(2, 4)
(1, 4)
(1, 2, 3)
(2, 3, 4)
(1, 2, 4)
(1, 3, 4)
(1, 2, 3, 4)

I wrote some more involved code which will print the powerset nicely (see the repo for pretty printing functions I've not included here: print_partitions, print_partitions_by_length, and pprint_tuple).

• Repo: ordered-powerset, specifically pset_partitions.py

This is all pretty simple, but still might be useful if you want some code that'll let you get straight to accessing the different levels of the powerset:

from itertools import permutations as permute
from numpy import cumsum

# http://jeromekelleher.net/generating-integer-partitions.html
# via
# https://mcmap.net/q/129093/-elegant-python-code-for-integer-partitioning-closed#comment25080713_10036764

def asc_int_partitions(n):
    a = [0 for i in range(n + 1)]
    k = 1
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2 * x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield tuple(a[:k + 2])
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield tuple(a[:k + 1])

# https://mcmap.net/q/129094/-permutations-with-unique-values
def uniquely_permute(iterable, enforce_sort=False, r=None):
    previous = tuple()
    if enforce_sort: # potential waste of effort (default: False)
        iterable = sorted(iterable)
    for p in permute(iterable, r):
        if p > previous:
            previous = p
            yield p

def sum_min(p):
    return sum(p), min(p)

def partitions_by_length(max_n, sorting=True, permuting=False):
    partition_dict = {0: ()}
    for n in range(1,max_n+1):
        partition_dict.setdefault(n, [])
        partitions = list(asc_int_partitions(n))
        for p in partitions:
            if permuting:
                perms = uniquely_permute(p)
                for perm in perms:
                    partition_dict.get(len(p)).append(perm)
            else:
                partition_dict.get(len(p)).append(p)
    if not sorting:
        return partition_dict
    for k in partition_dict:
        partition_dict.update({k: sorted(partition_dict.get(k), key=sum_min)})
    return partition_dict

def print_partitions_by_length(max_n, sorting=True, permuting=True):
    partition_dict = partitions_by_length(max_n, sorting=sorting, permuting=permuting)
    for k in partition_dict:
        if k == 0:
            print(tuple(partition_dict.get(k)), end="")
        for p in partition_dict.get(k):
            print(pprint_tuple(p), end=" ")
        print()
    return

def generate_powerset(items, subset_handler=tuple, verbose=False):
    """
    Generate the powerset of an iterable `items`.

    Handling of the elements of the iterable is by whichever function is passed as
    `subset_handler`, which must be able to handle the `None` value for the
    empty set. The function `string_handler` will join the elements of the subset
    with the empty string (useful when `items` is an iterable of `str` variables).
    """
    ps = {0: [subset_handler()]}
    n = len(items)
    p_dict = partitions_by_length(n-1, sorting=True, permuting=True)
    for p_len, parts in p_dict.items():
        ps.setdefault(p_len, [])
        if p_len == 0:
            # singletons
            for offset in range(n):
                subset = subset_handler([items[offset]])
                if verbose:
                    if offset > 0:
                        print(end=" ")
                    if offset == n - 1:
                        print(subset, end="\n")
                    else:
                        print(subset, end=",")
                ps.get(p_len).append(subset)
        for pcount, partition in enumerate(parts):
            distance = sum(partition)
            indices = (cumsum(partition)).tolist()
            for offset in range(n - distance):
                subset = subset_handler([items[offset]] + [items[offset:][i] for i in indices])
                if verbose:
                    if offset > 0:
                        print(end=" ")
                    if offset == n - distance - 1:
                        print(subset, end="\n")
                    else:
                        print(subset, end=",")
                ps.get(p_len).append(subset)
        if verbose and p_len < n-1:
            print()
    return ps

As an example, I wrote a CLI demo program which takes a string as a command line argument:

python string_powerset.py abcdef

⇣

a, b, c, d, e, f

ab, bc, cd, de, ef
ac, bd, ce, df
ad, be, cf
ae, bf
af

abc, bcd, cde, def
abd, bce, cdf
acd, bde, cef
abe, bcf
ade, bef
ace, bdf
abf
aef
acf
adf

abcd, bcde, cdef
abce, bcdf
abde, bcef
acde, bdef
abcf
abef
adef
abdf
acdf
acef

abcde, bcdef
abcdf
abcef
abdef
acdef

abcdef

Trenatrenail

Answer 30

Here it is my solutions, it is similar (conceptually) with the solution of lmiguelvargasf.

Let me say that -[math item] by defintion the powerset do contain the empty set -[personal taste] and also that I don't like using frozenset.

So the input is a list and the output will be a list of lists. The function could close earlier, but I like the element of the power set to be order lexicographically, that essentially means nicely.

def power_set(L):
    """
    L is a list.
    The function returns the power set, but as a list of lists.
    """
    cardinality=len(L)
    n=2 ** cardinality
    powerset = []
    
    for i in range(n):
        a=bin(i)[2:]
        subset=[]
        for j in range(len(a)):
            if a[-j-1]=='1':
                subset.append(L[j])
        powerset.append(subset)
        
    #the function could stop here closing with
    #return powerset

    powerset_orderred=[]
    for k in range(cardinality+1):
        for w in powerset:
            if len(w)==k:
                powerset_orderred.append(w)
        
    return powerset_orderred

Weathers

Answer 31

#I hope this will work for you

ab=['a','b', 'c']

for i in range(2**len(ab)):
    for j in range(len(ab)):
        if '1' in bin(i)[-1:-4:-1][j]:
            print(ab[j], end=" ")
    print()

Copula

Answer 32

def powerset(some_set):
    res = [(a,b) for a in some_set for b in some_set]
    return res

Biquarterly

While this code may answer the question, providing additional context regarding why and/or how this code answers the question improves its long-term value. Consider reading How to Answer and edit your answer to improve it. – Screen

What @Screen is always a good practice, but is especially important when you're answering a decade old question with 28 other answers. Why is this an improvement over the accepted answer? What does this answer contribute that the other answers don't offer? – Erek

Also, this code won't return the powerset of a set, but instead only a set of tuple with cardinal size 2 – Bouie