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:
“At the age of twelve I was finding the world too small: it appeared to me like a dull, trim back garden, in which only trivial games could be played.”
—Elizabeth Bowen (1899–1973)
“always keep a-hold of Nurse
For fear of finding something worse.”
—Hilaire Belloc (1870–1953)
“After mature deliberation of counsel, the good Queen to establish a rule and imitable example unto all posterity, for the moderation and required modesty in a lawful marriage, ordained the number of six times a day as a lawful, necessary and competent limit.”
—Michel de Montaigne (1533–1592)