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 affects men sharply about a foreign nation is not so much finding or not finding familiar things; it is rather not finding them in the familiar place.”
—Gilbert Keith Chesterton (1874–1936)
“There is no rule more invariable than that we are paid for our suspicions by finding what we suspected.”
—Henry David Thoreau (1817–1862)
“The quality of moral behaviour varies in inverse ratio to the number of human beings involved.”
—Aldous Huxley (1894–1963)