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:
“What Romantic terminology called genius or talent or inspiration is nothing other than finding the right road empirically, following one’s nose, taking shortcuts.”
—Italo Calvino (1923–1985)
“Why are we so full of restraint? Why do we not give in all directions? Is it fear of losing ourselves? Until we do lose ourselves there is no hope of finding ourselves.”
—Henry Miller (1891–1980)
“I heartily wish you, in the plain home-spun style, a great number of happy new years, well employed in forming both your mind and your manners, to be useful and agreeable to yourself, your country, and your friends.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)