# 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 lexicographic order colexicographic order prefix rotation (Ruskey-Williams' cool-lex) minimal-change order (BRGC-based) strong minimal-change order (Eades-McKay) two-close Gray code (Chase) Print set representation Output format graphics (≤500 objects) text (≤10000 objects) file (≤100000 objects)
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.

 Lex Colex Cool-lex MC EMK Chase

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].

## Enumeration (OEIS)

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

## References

• [BER76] J. R. Bitner, G. Ehrlich, and E. M. Reingold. Efficient generation of the binary reflected Gray code and its applications. Comm. ACM, 19(9):517–521, 1976.
• [Cha89] P. J. Chase. Combination generation and graylex ordering. Congr. Numer., 69:215–242, 1989. Eighteenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1988).
• [EM84] P. Eades and B. McKay. An algorithm for generating subsets of fixed size with a strong minimal change property. Inform. Process. Lett., 19(3):131–133, 1984.
• [Knu11] D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ, 2011.
• [PI79] W. H. Payne and F. M. Ives. Combination generators. ACM Trans. Math. Softw., 5(2):163–172, 1979.
• [RW05] F. Ruskey and A. Williams. Generating combinations by prefix shifts. In Computing and combinatorics, volume 3595 of Lecture Notes in Comput. Sci., pages 570–576. Springer, Berlin, 2005.
• [TL73] D. Tang and C. Liu. Distance-2 cyclic chaining of constant-weight codes. IEEE Trans. Computers, C-22:176–180, 1973.