Generating All Combinations of a Set

Let $A = \{ 1, 2, ..., n \}$ be a finite $n$-element set of positive integers. We have already seen from the Generating Permutations with Inversion Sequences and the An Alternative Method for Generating Permutations with Inversion Sequences two different methods for generating a list of all $n!$ of the $n$-permutations of elements from $A$. We will now look at a method for generating a list of all $2^n$ combinations of $A$ using the binary number system.

Now consider a finite $n$-element set $A = \{ x_{n-1}, x_{n-2}, ..., x_1, x_0 \}$. The combinations of $A$ are precisely subsets of $A$. Let $B \subseteq A$. Then for each $x_j \in A$ for $j \in \{ 0, 1, ..., n-1 \}$ we have that either $x_j \not \in B$ or $x_j \in B$.

Consider a finite sequence $(a_{n-1}, a_{n-2}, ..., a_1, a_0)$ of $n$ numbers where $a_{j} \in \{ 0, 1 \}$ for all $j \in \{0, 1, ..., n-1 \}$. For each $j$ we will define:

(1)

\begin{align} \quad a_j = \left\{\begin{matrix} 0 && \mathrm{if} \: x_j \not \in B\\ 1 && \mathrm{if} \: x_j \in B \end{matrix}\right. \end{align}

Then each of these sequences tells us which elements from $A$ are contained in the subset $B$.

For example, consider the set $A = \{x_3, x_2, x_1, x_0 \}$. Then the sequence $(a_3, a_2, a_1, a_0) = (1, 0, 1, 1)$ tells us that $B \subseteq A$ is such that $x_0 \in B$, $x_1 \in B$, $x_2 \not \in B$ and $x_3 \in B$, that is:

(2)

\begin{align} \quad B = \{ x_3, x_1, x_0 \} \subseteq \{ x_3, x_2, x_1, x_0 \} = A \end{align}

For another example, the sequence $(0, 0, 0, 0)$ implies that $B$ is a subset of $A$ containing no elements, that is $x_0, x_1, x_2, x_3 \not \in B$ and so:

(3)

\begin{align} \quad B = \emptyset \subseteq \{ x_3, x_2, x_1, x_0 \} = A \end{align}

Similarly, the sequence $(1, 1, 1, 1)$ implies that $B$ is a subset of $A$ containing all elements in $A$, that is $x_0, x_1, x_2, x_3 \in B$ and so:

(4)

\begin{align} \quad B = \{ x_3, x_2, x_1, x_0 \} \subseteq \{ x_3, x_2, x_1, x_0 \} = A \end{align}

For each of the examples above, consider $a_3a_2a_1a_0$ as binary digit representations of the corresponding subset $B$. From the subsets above, we have the digit representations $1011$, $0000$, and $1111$. These numbers translate from binary to decimal as $1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 11$, $0 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 0 \cdot 2^0 = 0$, and $1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 15$ respectively.

In general, for an $n$-element set $A = \{ x_{n-1}, x_{n-2}, ..., x_1, x_0 \}$ we have that each subset $B \subseteq A$ has a unique sequence in this manner, $(a_{n-1}, a_{n-2}, ..., a_1, a_0)$ for $a_j \in \{0, 1 \}$ for all $j \in \{0, 1, ..., n-1 \}$ as described above and such that the binary digit representation $a_{n-1}a_{n-2}...a_1a_0$ gives a decimal ($10$-usable digit) number $m$ where $0 \leq m < 2^n$ obtained by the formula:

(5)

\begin{align} \quad m = a_{n-1} \cdot 2^{n-1} + a_{n-2} \cdot 2^{n-2} + ... + a_1 \cdot 2^1 + a_0 \cdot 2^0 \end{align}

Theorem 1: Let $A = \{ x_{n-1}, x_{n-2}, ..., x_1, x_0 \}$ be a finite $n$-element set. Then all $2^n$ combinations/subsets $B$ of $A$ can be obtained by taking all decimal numbers $m$ such that $0 \leq m < 2^m$ and converting them to $n$-digit binary numbers $a_{n-1}a_{n-2}...a_1a_0$ where each $a_j \in \{0, 1 \}$ says that $a_j = 0$ implies $x_j \not \in B$ and $a_j = 1$ implies $x_j \in B$.

For example, suppose that we want to list all combinations of the elements in $A = \{x_2, x_1, x_0 \}$. There will be $2^3 = 8$ combinations. The table below illustrates the use of Theorem 1 to generate all $8$ of these combinations.

Decimal Number	Binary Number	Associated Binary Sequence	Combination
$0$	$000$	$(0, 0, 0)$	$\emptyset$
$1$	$001$	$(0, 0, 1)$	$\{ x_0 \}$
$2$	$010$	$(0, 1, 0)$	$\{ x_1 \}$
$3$	$011$	$(0, 1, 1)$	$\{ x_1, x_0 \}$
$4$	$100$	$(1, 0, 0)$	$\{ x_2 \}$
$5$	$101$	$(1, 0, 1)$	$\{ x_2, x_0 \}$
$6$	$110$	$(1, 1, 0)$	$\{ x_2, x_1 \}$
$7$	$111$	$(1, 1, 1)$	$\{ x_2, x_1, x_0 \}$