Make Your Own Power Set Function in Python

Let S be a set defined as follows:  $S = \left \{ 1, 2, 3 \right \}$.

What is the power set of S?

$\wp (S)= \left \{ \left \{  \right \}, \left \{ 1 \right \},\left \{ 2 \right \},\left \{ 3 \right \}, \left \{ 1,2 \right \}, \left \{ 1, 3 \right \}, \left \{ 2,3 \right \}, \left \{ 1,2,3 \right \} \right \}$

How do we generate it?

The power set of a set is the set of all subsets of that set. With a simple set like the one given above, this isn't too hard. However, as the number of elements in the set increases, the power set of that set becomes increasingly difficult to generate. For the set S above, and for any power set, we first throw in the empty set:

$\left \{ \left \{  \right \}, \right \}$

Next, we add in all of the singleton sets:

$ \left \{ \left \{  \right \}, \left \{ 1 \right \}, \left \{ 2 \right \}, \left \{ 3 \right \},\right \}$

Now, what?... Well, it's easy to see how we can make three distinct pairs (1, 2), (1, 3), and (2, 3), and then throw them into our growing set of subsets, but it doesn't help us to easily see how we can write the code for a function that would generate the power set. So, let's go back to just having:

$\left \{ \left \{  \right \}, \right \}$, and call it PS2B, for 'Power Set to Be'.

Now, from the main set S, bring out the first element as a singleton set and take the union of it with each individual member of PS2B, which for now means, taking the union of it with the empty set. If A is the empty set and B is the singleton set with element '1', we get:

$A\cup B = \left \{ 1 \right \}$

Now, you might be thinking, Why bother when we already knew that was an element of the power set? The next step will reveal why this method works...

So, now, PS2B looks like this:

$PS2B = \left \{ \left \{  \right \}, \left \{ 1 \right \} \right \}$

From the main set, we bring out the second element as a singleton set and take the union of it with each member of PS2B. If we let this singleton set with element '2' be called C, we have:

$A\cup C = \left \{ 2 \right \}$, and

$B\cup C = \left \{ 1, 2 \right \}$

We add these to PS2B to get:

$PS2B = \left \{ \left \{  \right \}, \left \{ 1 \right \}, \left \{ 2 \right \}, \left \{ 1,2 \right \} \right \}$

Aha! Things are coming together now!

Bring out the third element of the main set and take the union of it with each member of PS2B. Let D be the set containing the elements '1' and '2' (1, 2), and let E be the singleton set with element '3'. This gives us:

$A\cup E = \left \{ 3 \right \}$, and

$B\cup E = \left \{ 1,3 \right \}$, and

$C\cup E = \left \{ 2,3 \right \}$, and

$D\cup E = \left \{1,2,3 \right \}$.

Add these to PS2B and we get:

$PS2B = \wp (S) = \left \{ \left \{  \right \}, \left \{ 1 \right \}, \left \{ 2 \right \}, \left \{ 1, 2 \right \},\left \{ 3 \right \}, \left \{ 1,3 \right \}, \left \{ 2,3 \right \},\left \{ 1,2,3 \right \} \right \}$,

which is what we wanted. We were able to compute it using a simple method where we took each element out of the main set and iterated over a growing set (PS2B) until we grew that set into the power set P(S).

The python code for this function looks like: