Generate combinations

Generate all $k$-element subsets of an $n$-element ground set.
Size $n$ of ground set (max. 20)
Size $k$ of subsets (between 0 and $n$)
Algorithm
Print set representation
Output format
Output  numbering graphics

Object info

A combination describes in how many ways we can select $k$ elements of an $n$-element ground set. For instance, all 2-element subsets of $\{1,2,3,4\}$ are given by 12,13,14,23,24,34 (set brackets omitted for simplicity). A combination can also be represented by its characteristic vector, which is a bitstring of length $n$ which has a 1-bit at position $i$ if and only if the element $i$ is in the set. For instance, the characteristic vectors of the combinations from the previous example are 1100,1010,1001,0110,0101,0011, respectively. The following figure shows the result of all six algorithms running on this website for generating all combinations for $n=6$ and $k=3$, where 0=white and 1=black.

LexColexCool-lexMCEMKChase

All those algorithms are part of Jörg Arndt's FXT library. The algorithm for lexicographic ordering is explained as Algorithm L in Knuth's book [Section 7.2.1.3, Knu11]. The prefix rotation algorithm was discovered by Ruskey and Williams [RW05], and they named this ordering cool-lex in their paper. By restricting the binary reflected Gray code (BRGC) to bitstrings with a fixed Hamming weight (=number of 1s), we obtain a minimal-change order of combinations, where in each step only a single 0- and 1-bit are swapped. This was first observed by Tang and Liu [TL73], and the corresponding algorithm is described as Algorithm R in Knuth's book [Knu11] (see also [BER76, PI79]). In the algorithm due to Eades and McKay [EM84], we only allow swaps between a 0 and 1 where all bits in between are 0s. We can think of the 1-bits as pressed keys on a piano; then in each step only a single finger moves, and it does not cross the other fingers. In the two-close Gray code, we only allow swaps between a neighboring 0 and 1, or a 0 and 1 with a single 0 in between. The corresponding Gray code was first discovered by Chase [Cha89] and is described as Algorithm C in Knuth's book [Knu11].

Combinations are generalized by multiset permutations, and more algorithms for generating them can be found in that section.

Enumeration (OEIS)

The number of combinations is given by the binomial coefficients $\binom{n}{k}$, which is OEIS A007318.

Download source code

[Zipped C++ source code (GNU GPL)]
[Link to Jörg Arndt's FXT library (GNU GPL)]

References