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

 

2 thoughts to “Calculate power set (set of all subsets) in Python without recursion”

    1. Hi,

      first you have to understand what 1 << k means. “<<” is the bit-shift operator (to the left). This means that if k = 1, 1 is moved 1 position to the left.

      k = 1 (decimal) => 0001 (binary) << 1 = 0010 (binary) = 2 (decimal)
      k = 2 (decimal) => 0001 (binary) << 2 = 0100 (binary) = 4 (decimal)
      and so on…

      “&” is the bit-wise and operator. It takes two integers, looks at their binary representation and returns an integer that has 1 in the binary representation at every position where the two input integers both have a 1.

      Example:
      a = 5 (decimal) = 0101 (binary)
      b = 3 (decimal) = 0011 (binary)
      => a & b = 0101 & 0011 = 0001 (binary) = 1 (decimal)

      a = 2d = 0010b
      b = 6d = 0110b
      => a & b = 0010b & 0110b = 0010b = 2

      In this algorithm, the right side of the bit-wise and is always a power of 2. This means that the binary representation has exactly one 1 in it and every other position is 0.
      In general: 1 << k = 2^k
      So i & 1 << k basically checks if the number i has a 1 at position k in its binary representation. If yes, element k is included in subset i.

      I hope this helps you

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.