Editing Combination (section)

=== Enumerating ''k''-combinations ===

One can [[enumeration|enumerate]] all ''k''-combinations of a given set ''S'' of ''n'' elements in some fixed order, which establishes a [[bijection]] from an interval of <math>\tbinom nk</math> 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&nbsp;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.<ref>{{cite web|url=http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf |archive-date=2022-10-09 |url-status=live |title=Generating Elementary Combinatorial Objects |author=Lucia Moura |website=Site.uottawa.ca |access-date=2017-04-10}}</ref><ref>{{cite web|url=http://www.sagemath.org/doc/reference/sage/combinat/subset.html |format=PDF |title=SAGE : Subsets |website=Sagemath.org |access-date=2017-04-10}}</ref>

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.