power-set

Power Set

Power set of a set S is the set of all of the subsets of S, including the empty set and S itself. Power set of set S is denoted as P(S).

For example for {x, y, z}, the subsets are:

{
  {}, // (also denoted empty set ∅ or the null set)
  {x},
  {y},
  {z},
  {x, y},
  {x, z},
  {y, z},
  {x, y, z}
}

Here is how we may illustrate the elements of the power set of the set {x, y, z} ordered with respect to inclusion:

Number of Subsets

If S is a finite set with |S| = n elements, then the number of subsets of S is |P(S)| = 2^n. This fact, which is the motivation for the notation 2^S, may be demonstrated simply as follows:

First, order the elements of S in any manner. We write any subset of S in the format {γ1, γ2, ..., γn} where γi , 1 ≤ i ≤ n, can take the value of 0 or 1. If γi = 1, the i-th element of S is in the subset; otherwise, the i-th element is not in the subset. Clearly the number of distinct subsets that can be constructed this way is 2^n as γi ∈ {0, 1}.

Algorithms

Bitwise Solution

Each number in binary representation in a range from 0 to 2^n does exactly what we need: it shows by its bits (0 or 1) whether to include related element from the set or not. For example, for the set {1, 2, 3} the binary number of 0b010 would mean that we need to include only 2 to the current set.

	abc	Subset
0	000	{}
1	001	{c}
2	010	{b}
3	011	{c, b}
4	100