structural:scholar_edition
Enumerating k -combinations

One can enumerate all k -combinations of a given set S of n elements in some fixed order, which establishes a bijection from an interval of (n k) {\displaystyle {\tbinom {n}{k}}} integers with the set of those k -combinations. Assuming S is itself ordered, for instance S = { 1, 2,..., n }, there are two natural possibilities for ordering its k -combinations: by comparing their smallest elements first (as in the illustrations above) or by comparing their largest elements first. The latter option has the advantage that adding a new largest element to S will not change the initial part of the enumeration, but just add the new k -combinations of the larger set after the previous ones. Repeating this process, the enumeration can be extended indefinitely with k -combinations of ever larger sets. If moreover the intervals of the integers are taken to start at 0, then the k -combination at a given place i in the enumeration can be computed easily from i, and the bijection so obtained is known as the combinatorial number system. It is also known as "rank"/"ranking" and "unranking" in computational mathematics.

There are many ways to enumerate k combinations. One way is to track k index numbers of the elements selected, starting with {0.. k −1} (zero-based) or {1.. k } (one-based) as the first allowed k -combination. Then, repeatedly move to the next allowed k -combination by incrementing the smallest index number for which this would not create two equal index numbers, at the same time resetting all smaller index numbers to their initial values.