Finding The k-combination For A Given Number
The given formula allows finding the place in the lexicographic ordering of a given k-combination immediately. The reverse process of finding the k-combination at a given place N requires somewhat more work, but is straightforward nonetheless. By the definition of the lexicographic ordering, two k-combinations that differ in their largest element ck will be ordered according to the comparison of those largest elements, from which it follows that all combinations with a fixed value of their largest element are contiguous in the list. Moreover the smallest combination with ck as largest element is, and it has ci = i − 1 for all i < k (for this combination all terms in the expression except are zero). Therefore ck is the largest number such that . If k > 1 the remaining elements of the k-combination form the k − 1-combination corresponding to the number in the combinatorial number system of degree k − 1, and can therefore be found by continuing in the same way for and k − 1 instead of N and k.
Read more about this topic: Combinatorial Number System
Famous quotes containing the words finding the, finding and/or number:
“Love has its own instinct, finding the way to the heart, as the feeblest insect finds the way to its flower, with a will which nothing can dismay nor turn aside.”
—Honoré De Balzac (1799–1850)
“Primitive peoples tried to annul death by portraying the human body—we do it by finding substitutes for the human body. Technology instead of mysticism!”
—Max Frisch (1911–1991)
“In proportion as our inward life fails, we go more constantly and desperately to the post office. You may depend on it, that the poor fellow who walks away with the greatest number of letters, proud of his extensive correspondence, has not heard from himself this long while.”
—Henry David Thoreau (1817–1862)