Calculate power set (set of all subsets) in Python without recursion

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 iterative approach which is faster than the recursive one.

def get_subsets(fullset):
  listrep = list(fullset)

  subsets = []
  for i in range(2**len(listrep)):
    subset = []
    for k in range(len(listrep)):			
      if i & 1<<k:
        subset.append(listrep[k])
    subsets.append(subset)		

  return subsets

subsets = get_subsets(set([1,2,3,4]))
print(subsets)
print(len(subsets))

You can also find a shorter version at the end of the article, but to understand the principle the algorithm above is more suitable.

A powerset of a set with \(n\) elements always contains \(2^n\) elements. For example, the power set of \(\{1,2\}\) is \(\{\{\}, \{1\}, \{2\}, \{1,2\}\}\)

By iterating from \(0\) to \(2^n\) we iterate \(2^n\) times and the binary representation of every iteration index can be used to determine whether to include an element from the original set or not.

For example, iteration 0 would be represented by 0…0, so we would not include any element and produce the empty set which is a subset of every set.

Iteration 0…01 would only include element 1 as there is only one 1 in the binary representation of the iteration index. 0…0101 would add the subset containing element 1 and 3, and so on.

The inner loop iterates from \(k=0\) to \(k=n\) and \(i \& 1<<k\) is true when there is a 1 in the binary representation at the index corresponding to element k.

Please note that this algorithm makes use of big integers, so if you want to calculate the power set of a set containing more than 32 elements (or 64 on 64 bit systems) you will run into overflow problems and then should better use a recursive approach.

Here is a more pythonic solution that uses list comprehensions:

def get_subsets(fullset):
  listrep = list(fullset)
  n = len(listrep)
  return [[listrep[k] for k in range(n) if i&1<<k] for i in range(2**n)]

 

Leave a Reply

Your email address will not be published. Required fields are marked *