Power set of a set

Introduction

To follow up on my interview questions series, let's look at this problem today:

This problem was asked by Google.
The power set of a set is the set of all its subsets. Write a function that, given a set, generates its power set.
For example, given the set {1, 2, 3}, it should return {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
You may also use a list or array to represent a set.

Let's see how we can solve this.

Initial observations: size of the power set

Before we even start, we need to know what the size of the power set will be for a given initial set.

That is easy, since it's written on the problem statement itself: it's the size of the set of all its subsets. So we need to count the number of all subsets of our initial set.

That is taken by counting all subsets of our set. But how can we do it?

We see that, when building a certain subset, for every number we encounter in the original set, we can do one of two things:

• we consider this number in our subset;

• we don't consider the number in our subset;

So, for every single number, we have two choices.

If we take the product of these choices for each number, we get the total number of subsets. So the total number of subsets for the set, for example, {1, 2} will be:

{}, {1}, {2}, {1,2}

which is the same as 2^(num elements of initial set)

How to enumerate each set: properties of powers of 2

Now that we know the actual number of subsets we need to enumerate, all that's left is to actually enumerate them.

To do that, we can notice that we can either choose or not choose a single element to go in the set, which is how we got to the total count in the first place. If we count from 0 to (num elements in the original set - 1) in binary, we can encode this exact property.
Summing 1 in binary is the same as adding 1 to the rightmost bit of the number, with carry being added to the bit immediately to the left of the highest bit set, and setting all others to 0. That's why 3 is 11b and 4 is 100b: carry from the highest set bit goes to the bit above and all others are set to 0.
For the purpose of generating a power set, when we have a set bit at position i, we take the ith element as part of our subset.

Then, to solve the original problem, we iterate from 1 to 2^(num elements of initial set), taking the binary representation of each number, left-padded with leading zero bits to match the length of the largest power of two (last element of the loop), keeping elements of the original set on set bits and leaving out the elements on the positions of the 0-bit.
To finish, we append the empty set to our result.

Python implementation

Here's the Python implementation of the described approach:

zipFunction = lambda a,b: b if a=='1' else None
def powerSet(s):
  powerset = []
  for i in range(1,2**len(s)):
    zippedList = [ zipFunction(a,b) for (a,b) in list((zip((['0']*(len(s) - len(list(bin(i)[2:])))+list(bin(i)[2:])),s)))]
    powerset.append(list(filter(lambda v: v!=None ,zippedList)))
  powerset.append([])  
  return sorted(powerset)

And running it yields:

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

Conclusion

To solve this problem, we needed to understand how deciding to choose or not choose a certain element of the original set maps to counting up to 2^(num elements in original set) in binary and using the bits to select our values.
Hope you liked reading! Until next time!