Ordering Combinations
A k-combination of a set S is a subset of S with k (distinct) elements. The main purpose of the combinatorial number system is to provide a representation, each by a single number, of all possible k-combinations of a set S of n elements. Choosing, for any n, {0, 1, ..., n − 1} as such a set, it can be arranged that the representation of a given k-combination C is independent of the value of n (although n must of course be sufficiently large); in other words considering C as a subset of a larger set by increasing n will not change the number that represents C. Thus for the combinatorial number system one just considers C as a k-combination of the set N of all natural numbers, without explicitly mentioning n.
In order to ensure that the numbers representing the k-combinations of {0, 1, ..., n − 1} are less than those representing k-combinations not contained in {0, 1, ..., n − 1}, the k-combinations must be ordered in such a way that their largest elements are compared first. The most natural ordering that has this property is lexicographic ordering of the decreasing sequence of their elements. So comparing the 5-combinations C = {0,3,4,6,9} and C' = {0,1,3,7,9}, one has that C comes before C', since they have the same largest part 9, but the next largest part 6 of C is less than the next largest part 7 of C'; the sequences compared lexicographically are (9,6,4,3,0) and (9,7,3,1,0). Another way to describe this ordering is view combinations as describing the k raised bits in the binary representation of a number, so that C = {c1,...,ck} describes the number
(this associates distinct numbers to all finite sets of natural numbers); then comparison of k-combinations can be done by comparing the associated binary numbers. In the example C and C' correspond to numbers 10010110012 = 60110 and 10100010112 = 65110, which again shows that C comes before C'. This number is not however the one one wants to represent the k-combination with, since many binary numbers have a number of raised bits different form k; one wants to find the relative position of C in the ordered list of (only) k-combinations.
Read more about this topic: Combinatorial Number System
Famous quotes containing the words ordering and/or combinations:
“Seeing then that truth consisteth in the right ordering of names in our affirmations, a man that seeketh precise truth, had need to remember what every name he uses stands for; and to place it accordingly; or else he will find himself entangled in words, as a bird in lime-twigs; the more he struggles, the more belimed.”
—Thomas Hobbes (1579–1688)
“You should try to understand every thing you see and hear; to act and judge for yourselves; to remember you each have a soul of your own to account for; M a mind of your own to improve. When you once get these ideas fixed, and learn to act upon them, no man or set of men, no laws, customs, or combinations of them can seriously oppress you.”
—Jane Grey Swisshelm (1815–1884)