Generating k-Combinations of a Set

Generating k-Combinations of a Set

Recall from the Generating All Combinations of a Set page that if $A = \{x_{n-1}, x_{n-2}, ..., x_1, x_0 \}$ is a finite $n$-element set then all of the $2^n$ combinations of elements of $A$ i.e., all of the $2^n$ subsets $B$ of $A$ can be obtained by assigning each subset in $A$ a binary number $a_{n-1}a_{n-2}...a_1a_0$ where for each $a_j \in \{ 0, 1 \}$ for $j \in \{0, 1, ..., n-1 \}$ we have that $a_j = 0$ implies that $x_j \not \in B$ and if $a_j = 1$ then $x_j \in B$

Suppose instead of generating ALL possible combinations/subsets of elements from $A$ that instead we only want to generate all $k$-combinations (or $k$-element subsets) of $A$. Of course, this can be accomplished with the algorithm described above with the throwaway of all subsets $B$ where $\lvert B \rvert \neq k$ but as we will see, there is a more efficient algorithm that allows for us to only generate the $k$-combinations.

Consider the set $A = \{1, 2, 3, 4, 5 \}$. There will be precisely $\binom{5}{2} = \frac{5!}{2!3!} = 10$ many $2$-combinations of elements from $A$. They are:

(1)
\begin{align} \quad (1, 2) \quad , \quad (1, 3) \quad , \quad (1, 4) \quad , \quad (1, 5) \quad , \quad (2, 3) \\ \quad (2, 4) \quad , \quad (2, 5) \quad , \quad (3, 4) \quad , \quad (3, 5) \quad , \quad (4, 5) \end{align}

It would be nice to induce some sort of ordering of these $2$-combinations. One such way is determine whether a certain combination/subset precedes another as defined below.

Definition: If $A = \{1, 2, ..., n \}$ is a finite $n$-element set of positive integers and if $B, C \subseteq A$ are $k$-subsets of $A$ then $B$ is said to Precede $C$ (or equivalently, $C$ Succeeds $B$) if the smallest integer $p$ where $p \in B \cup C$ and $p \not \in B \cap C$ is such that $p \in B$.

For example, consider the set $A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}$ and let $B = \{1, 4, 5, 7, 9 \}$ and $C = \{ 1,3, 4, 6, 9 \}$. Does $B$ precede $C$ or does $C$ precede $B$?

We have that then $B \cup C = \{1, 3, 4, 5, 6, 7, 9 \}$ and $B \cap C = \{1, 4, 9\}$. The smallest integer $p$ such that $p \in B \cup C$ and $p \not \in B \cap C$ is $p = 3$ and $p = 3 \in C$. Therefore $C$ precedes $B$.

We can now formulate a theorem for describing all of the $k$-combinations of elements from a subset of $n$-elements.

Lemma 1: Let $A = \{1, 2, ..., n \}$ be a finite $n$-element set of positive integers and for all positive integers $k$ such that $0 \leq k \leq n$ let all $k$-subsets $B$ of $A$ be of the form $B = \{b_1, b_2, ..., b_k \}$ where $1 \leq b_1 < b_2 < ... < b_k \leq n$. Then the $k$-subset that precedes all others is $\{1, 2, ..., k \}$ and the $k$-subset that succeeds all others is $\{ n - k +1, n - k + 2, ..., n - 1, n \}$.
  • Proof: Consider a $k$-subset $B = \{b_1, b_2, ..., b_k \}$ of $A$ where $B \neq \{1, 2, ..., k \}$. The largest element in $\{ 1, 2, ..., k \}$ is $k$. Let's determine a lower bound for the largest element $b_k$ in $B$. We must have that $0 \leq b_1 < b_2 < ... < b_k \leq n$. If $b_k = k$ then by The Pigeonhole Principle we must have that $b_1 = 1$, $b_2 = 2$, …, $b_k = k$ and so $B = \{ 1, 2, ..., k \}$ which is a contradiction. Thus the largest element $b_k > k$. Therefore there exists a smallest positive integer $p \in \{1, 2, ..., k \}$ such that $p \not \in B$. So $p \in B \cup \{1, 2, ..., k \}$ and $p \not \in B \cap \{1, 2, ..., k \}$ and $p$ is the smallest integer where $p \in \{1, 2, ..., n \}$ so $\{1, 2, ..., n \}$ precedes all other subsets $B$.
  • Now consider a $k$-subset $B = \{b_1, b_2, ..., b_k \}$ of $A$ where $B \neq \{n - k + 1, n - k + 2, ..., n - 1, n \}$ The smallest element in $\{n - k + 1, n - k + 2, ..., n - 1, n \}$ is $n - k + 1$ so let's determine an upper bound for the smallest element $b_1$ in $B$. If $b_1 = n - k + 1$ then by the pigeonhole principle we must have that $b_2 = n - k + 2$, …, $b _{k-1} = n - 1$ and $b_k = n$ and so $B = \{n - k + 1, n - k + 2, ..., n - 1, n \}$ which is a contradiction. Thus the smallest element $b_1 < n - k + 1$. Thus $b_1$ is the smallest integer such that $b_1 \in B \cup \{ n - k + 1, n - k + 2, ..., n - 1, n \}$ and $b_1 \not \in B \cap \{n - k +1, n - k +2, ..., n - 1, n \}$ and $b_1 \in B$ so $\{n - k +1, n - k + 2, ..., n - 1, n \}$ succeeds all other subsets $B$. $\blacksquare$
Theorem 1: Let $A = \{1, 2, ..., n \}$ be a finite $n$-element set of positive integers and for positive integers $k$ such that $0 \leq k \leq n$ let all $k$-subsets $B$ of $A$ be of the form $B = \{b_1, b_2, ..., b_k \}$ where $0 \leq b_1 < b_2 < ... < b_k \leq n$. Let the subset $B$ be such that $B \neq \{n - k + 1, n - k +2, ..., n - 1, n \}$. If $p$ is the largest integer where $b_p < n$ and $b_p + 1 \neq b_q$ for all $q \in \{ p + 1, p + 2, ..., k \}$. Then the subset $B^* = \{b_1, b_2, ..., b_{p-1}, b_p, b_p + 1, ..., b_p + k - p + 1 \}$ immediately succeeds $B$.
  • Proof: Consider the set $B$:
(2)
\begin{align} \quad B = \{b_1, b_2, ..., b_k \} = \{ b_1, b_2, ..., b_{p-1}b_p, ... , b_k \} \end{align}
  • This subset begins with the elements $b_1, b_2, ..., b_{p-1}, b_p$. Now consider the set $B^*$:
(3)
\begin{align} \quad B^* = \{b_1, b_2, ..., b_{p-1}, b_p, b_p + 1, ..., b_p + k - p + 1 \} \end{align}
  • This subset also begins with the elements $b_1, b_2, ..., b_{p-1}, b_p$. The difference between $B$ and $B^*$ are with the elements $b_{p+1} \in B$ and $b_p + 1 \in B^*$. Since $b_p + 1 \neq b_{p+1}$, $b_p + 1 \neq b_{p+2}$, …, $b_p + 1 \neq b_k$ we must have that the element $b_p + 1$ lies in between two elements in $\{ b_{p+1}, b_{p+2}, ..., b_{k} \}$ or after $b_k$. Regardless, the smallest number that $B$ and $B^*$ do NOT share in common will be $b_p + 1$ and $b_p + 1 \in B^*$, so $B^*$ succeeds $B$.
  • We now need to show that $B^*$ immediately succeeds $B$. Consider another set $B^+$ and suppose that $B^+$ starts with $b_1, b_2, ..., b_p$ and precedes $B^*$. Then the element $b_p^+ +1$ must lie between $b_p$ and $b_p + 1$, but this cannot happen. Furthermore, there are no numbers integers between $b_p+1$, $b_p + 2$, …, $b_p + k - p + 1$ (since these numbers are consecutively ordered) so $B^*$ immediately succeeds $B$. $\blacksquare$
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License