Computing Power Sets - Vancouver Computer Science Tutoring

Introduction to Power Sets

This blog post describes what power sets are and how to compute them recursively. After reading this post, you should understand how to derive the power set of a given set, and appreciate the immense computational expense of computing a power set.

What is a Power Set?

Given a set of objects $S$, the power set of that set, denoted $\mathcal{P}(S)$, is the set of all possible subsets of $S$.

Since that was quite a sentence to read, let’s break it down. Consider a set of three people who could be assigned to a certain software development task:

S = {Alice, Bob, Carol}

One possible subset of the available people to be assigned to the task is: {Alice, Carol}. There are also two edge cases to consider. The set of nobody, {}, is a subset of S. The set of everybody, {Alice, Bob, Carol}, is also a subset of S.

So, the set of all possible subsets — the power set of S — includes nobody, everybody, and all combinations of just some of the people:

$\mathcal{P}(S)$ = { {}, {Alice}, {Bob}, {Carol}, {Alice, Bob}, {Alice, Carol}, {Bob, Carol}, {Alice, Bob, Carol} }

The Recursive Property

One property of a power set is that it can be defined recursively. Note what happens if we omit Alice from our set, and compute the power set of the remaining people:

$T$ = {Bob, Carol}
$\mathcal{P}(T)$ = { {}, {Bob}, {Carol}, {Bob, Carol} }

We can compute the power set of $S$ (the set of all three people) by taking all the elements of $\mathcal{P}(T)$, plus all the elements of $\mathcal{P}(T)$ with Alice added to them:

The original value of $\mathcal{P}(T)$ = { {}, {Bob}, {Carol}, {Bob, Carol} }

The value of $\mathcal{P}(T)$ with Alice added to every element = { {Alice}, {Alice, Bob}, {Alice, Carol}, {Alice, Bob, Carol} }

The union of those two sets gives us the power set of S.

Recursively Computing a Power Set

Let’s consider a more formal definition of the recursive property shown above. The power set of the empty set — that is, the set of all possible subsets of the empty set — is the set containing the empty set:

$\mathcal{P}($ {} $)$ = { {} }

To make that easier to read, we’ll often see {} written as $\emptyset$. So:

$\mathcal{P}( \emptyset ) = \{ \emptyset \}$

For sets S that aren’t the empty set:

1. Choose some $e \in S$
2. Let $T = S \setminus \{e\}$
3. $\mathcal{P}(S) = \mathcal{P}(T) \cup \{ t \cup \{e\}~|~t \in \mathcal{P}(T) \}$

The Computation in Pseudocode

As an exercise, I recommend that students implement the formal recursive definition in their favourite programming language. Feel free to use lists instead of sets if it makes this exercise easier in your language of choice:

function powerSet(S)
  if S = {}
    return { {} }
  e <- some element of S
  T <- copy of S, but with e removed
  PT <- powerSet(T)
  PS <- copy of PT
  for each t in PT
    t_with_e <- copy of t
    add e to t_with_e
    add t_with_e to PS
  return PS

The Size of a Power Set

Consider a binary number with 8 bits. Every bit has one of 2 values (0 or 1). As such, there are $2^8$ possible values for that binary number.

Similarly consider a set of people $S$. In every subset of $S$, each person is either included or not included. So, there are $2^{|S|}$ possible subsets of $S$. That means $|\mathcal{P}(S)| = 2^{|S|}$. When $S$ was the set of 3 people (Alice, Bob, and Carol), the size of the power set of $S$ is $2^3 = 8$. But, if there were 6 people, the size of the power set of $S$ would be $2^6 = 64$.

The size of the power set of S grows exponentially with the size of S. Power sets can become massive in size!

Let’s look at some examples, with the scale of these numbers coming from Bruce Schneier’s excellent text, “Applied Cryptography” 2ed:

If you have 30 people, the size of the power set is roughly the number of years until the sun goes nova;
If you have 34 people, the size of the power set is roughly the age of the universe in years;
If you have 61 people, the size of the power set is roughly the total lifetime of the universe measured in seconds (under certain assumptions about the nature of our universe); and,
If you have 67 people, the size of the power set is roughly the number of atoms in our galaxy.

So, be careful about computing the power set of large sets. Even if your code is correct, your computation won’t end — at least, not before the potential end of the universe ends your computation.

Summary

A power set is itself a set, and it contains all possible subsets of the original set. It can be used to show, for example, all possible sets of people that could be assigned to a programming task.

A recursive definition of power sets lends itself to an algorithmic way of computing power sets — one which I encourage all students to try in a programming language of their choice. But, be careful about trying to compute a power set of a very large set. Your algorithm may be correct, yet not finish in your lifetime.

For more tips, and to arrange for personalized tutoring for yourself or your study group, check out Vancouver Computer Science Tutoring.