How to get all subsets of a set powerset

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

User · Answer

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.

User · Answer

def powerset lst       return reduce lambda result  x  result    subset    x  for subset in result                     lst

User · Answer

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        quot powerset  1 2 3   -- gt      1    2    3    1 2   1 3   2 3   1 2 3  quot      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  quot lexicographic quot  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   quot a quot   quot b quot   quot c quot   quot d quot   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   stackoverflow com questions 10035752 elegant-python-code-for-integer-partitioning 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  lt   y              a k    x             y -  x             k    1         l   k   1         while x  lt   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   stackoverflow com a 6285330 2668831 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  gt  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  quot  quot           for p in partition dict get k               print pprint tuple p   end  quot   quot           print       return  def generate powerset items  subset handler tuple  verbose False        quot  quot  quot      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        quot  quot  quot      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  gt  0                          print end  quot   quot                       if offset    n - 1                          print subset  end  quot  n quot                       else                          print subset  end  quot   quot                   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  gt  0                          print end  quot   quot                       if offset    n - distance - 1                          print subset  end  quot  n quot                       else                          print subset  end  quot   quot                   ps get p len  append subset          if verbose and p len  lt  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

User · Answer

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

User · Answer

Getting all the subsets with recursion  Crazy-ass one-liner  from typing import List  def subsets xs  list  - gt  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  - gt    a   subsets           subsets  x xs    map  x    subsets xs     subsets xs

User · Answer

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

User · Answer

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  amp   1  lt  lt  j    gt  0               print set j   end           print     set     a    b    c   printPowerSet set 3

User · Answer

There is a refinement of powerset   def powerset seq               Returns all the subsets of this set  This is a generator              if len seq   lt   0          yield        else          for item in powerset seq 1                 yield  seq 0   item             yield item

User · Answer

Here is more code for a powerset  This is written from scratch    gt  gt  gt  def powerset s           x   len s          for i in range 1  lt  lt  x               print  s j  for j in range x  if  i  amp   1  lt  lt  j         gt  gt  gt  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  lt  lt  x  to for i in range 1  1  lt  lt  x      Returning to this years later  I d now write it like this   def powerset s       x   len s      masks    1  lt  lt  i for i in range x       for i in range 1  lt  lt  x           yield  ss for mask  ss in zip masks  s  if i  amp  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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

def powerset some set       res     a b  for a in some set for b in some set      return res

User · Answer

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        quot  quot  quot      L is a list      The function returns the power set  but as a list of lists       quot  quot  quot      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

User · Answer

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

User · Answer

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  lt  lt  length               subset                  for i in range length                   if max int  amp   0x1  lt  lt  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

User · Answer

The Python itertools page has exactly a powerset recipe for this   from itertools import chain  combinations  def powerset iterable        powerset  1 2 3   -- gt      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    gt  gt  gt  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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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  gt  0 else

User · Answer

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

User · Answer

Use function powerset   from package more itertools      Yields all possible subsets of the iterable    gt  gt  gt  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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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    set   takes an iterable  so set set    will return set   because the empty set iterable is empty  duh I guess     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

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

Examples related to python

Examples related to set

Examples related to powerset