- Combinadic
In
mathematics , a combinadic is an orderedinteger partition , or composition. Combinadics provide alexicographical index forcombination s. Applications for combinadics includesoftware testing , sampling,quality control , and the analysis ofgambling games such as Canada's national 6/49 lottery.For definiteness, we will consider the "k"-combinations on the set "S" = {0, 1, ..., "n" − 1} of the first "n" integers starting from 0. Recall that there are C("n","k") = "n"! / ( "k"! ("n" − "k")! ) of these. The index we are looking for is the mapping associating the numbers "i" = 0, 1, ..., C("n","k") − 1 with the list of "k"-combinations having their elements written in ascending order, and themselves ordered lexicographically. By
abuse of notation we denote as C("n","k")("i") the "i"th "k"-combination taken from the set of "n" elements. Then the index for the ten 3-combinations of the set of five elements {0, 1, 2, 3, 4} can be written out as follows."i"th 3-combination Index "i" C(5,3)("i") 0 {0, 1, 2} 1 {0, 1, 3} 2 {0, 1, 4} 3 {0, 2, 3} 4 {0, 2, 4} 5 {0, 3, 4} 6 {1, 2, 3} 7 {1, 2, 4} 8 {1, 3, 4} 9 {2, 3, 4}
The definition we want for an "i"th combinadic M("n","k")("i") on the C("n","k") "k"-combinations of the set of "n" elements is most directly achieved by first considering the list of all possible words "n" letters long consisting of "k" 1s and "n" − "k" 0s. We designate the letter positions, or places, in the word as "n" − 1, "n" − 2, ..., 1, 0 in descending order, lowest letter position on the right. Then the "i"th combinadic in this system is defined to be the ordered "n"-tuple consisting of the letter positions for the 1s in the "n"th word in
lexicographical order , reading from left to right.We can now write out the combinadics for the ten 3-combinations of the set of five elements in the following table.
"i"th word (places) "i"th combinadic Index "i" (43210) M(5,3)("i")
|||
0 00111 (2, 1, 0) 1 01011 (3, 1, 0) 2 01101 (3, 2, 0) 3 01110 (3, 2, 1) 4 10011 (4, 1, 0) 5 10101 (4, 2, 0) 6 10110 (4, 2, 1) 7 11001 (4, 3, 0) 8 11010 (4, 3, 1) 9 11100 (4, 3, 2)Clearly the combinadics also list all the "k"-combinations from the set of "n" elements in lexicographical order, but here the elements are listed in "decreasing", not increasing order. In [http://msdn2.microsoft.com/en-us/library/aa289166(VS.71).aspx this MSDN article] ,
James D. McCaffrey shows that the conventional combinations index is easily obtained from the combinadics.The more useful composition-based definition for a combinadic can be illustrated using an example. Consider the combinadic with index 72 in the system of 5-combinations from the set of 10 elements. This is M(10,5)(72) = (8, 6, 3, 1, 0). By studying the seventy-three words consisting of five 1s and five 0s that lead up to this combinadic, it becomes clear that there is a simple relationship between the numbers in the combinadic code and an ordered partition of the index number. R "i"th word e Index Breakdown of Index (places) "i"th combinadic f "i" (9876543210) M(10,5)("i")
||||||||
A) 0 0000011111 (4,3,2,1,0) 1 0000101111 (5,3,2,1,0) 2 0000110111 (5,4,2,1,0) 3 0000111011 (5,4,3,1,0) 4 0000111101 (5,4,3,2,0) 5 0000111110 (5,4,3,2,1) 6 0001001111 (6,3,2,1,0) 7 0001010111 (6,4,2,1,0) ... ... ... ... 53 0011110010 (7,6,5,4,1) 54 0011110100 (7,6,5,4,2) B) 55 C(8,5) − 1 0011111000 (7,6,5,4,3) C) 56 C(8,5) 0100001111 (8,3,2,1,0) ^ ^ 57 0100010111 (8,4,2,1,0) 58 0100011011 (8,4,3,1,0) 59 0100011101 (8,4,3,2,0) 60 0100011110 (8,4,3,2,1) 61 0100100111 (8,5,2,1,0) ... ... ... ... 67 0100110110 (8,5,4,2,1) 68 0100111001 (8,5,4,3,0) 69 0100111010 (8,5,4,3,1) D) 70 C(8,5) + C(6,4) − 1 0100111100 (8,5,4,3,2) E) 71 C(8,5) + C(6,4) 0101000111 (8,6,2,1,0) ^ ^ ^ ^ F) 72 C(8,5) + C(6,4) + C(3,3) + C(1,2) + C(0,1) 0101001011 (8,6,3,1,0) ^ ^ ^ ^ ^ ^ ^ ^ ^ ^Notice first of all that between reference A and reference B, the five 1s run through all the possible patterns among the eight rightmost places 0, 1, 2, ..., 7 in the word. There are C(8, 5) = 56 of these, so since reference A is at index 0, reference B has to be at index C(8,5) − 1 = 55. At the next index, reference C, the leftmost 1 achieves its final resting place of position 8 on index C(8,5) = 56, while the remaining four 1s are reset to the far right of the word. Next notice that between reference C and reference D, the remaining four 1s run through all the possible patterns in the six rightmost places 0, 1, 2, ..., 5 in the word. There are C(6,4) = 15 of these, so reference D lies at index C(8,5) + C(6,4) − 1 = 70, and the next index, reference E, where the second leftmost 1 achieves its final resting place of position 6 and the remaining three 1s are reset to the right, is index C(8,5) + C(6,4) = 71. The three rightmost 1s run through the single (C(3,3) = 1) pattern on the three rightmost places before the third rightmost 1 takes up its final station at place 3 at reference F. The two rightmost 1s run through no (C(1,2) = 0) patterns before the second rightmost 1 doesn't move; similarly the one rightmost 1 runs through no (C(0,1) = 0) patterns before it doesn't move.The relationship between combinadics and ordered integer partitions is formalized in the following.
; Definition : (after McCaffrey); combinadic : In the context of the system of "C"("n", "k") "k"-combinations on the set of "n" objects, and for each non-negative integer "i" less than C("n","k"), the "i"th combinadic "M"("n","k")("i") is the unique strictly decreasing
sequence ("m""k"−1, "m""k"−2, ..., "m"0) of "k" integers lying between "n" − 1 and 0 so that "C"(m"k"−1,"k") + "C"("m""k"−2,"k" − 1) + ... + "C"("m"0,1) = "i".Clearly the index value "i" for any combinadic can be immediately calculated from its elements.
To get the elements of the combinadic "M"("n","k")("i") from its index "i", we first find the largest first element "m""k"−1 so that C(m"k"−1, "k") is less than or equal to "i". The second element is found by repeating the procedure in the reduced combinadic system where "i" is reduced by the previous C(m"k"−1,"k"), "n" is set to the previous m"k"−1, and "k" is reduced by one. This is continued until "k" is reduced to zero. As McCaffrey points out in [http://msdn.microsoft.com/library/en-us/dv_vstechart/html/mth_lexicograp.asp his MSDN article] , efficiently finding the largest "m""k"−1 is the key to calculating a "k"-combination from its index value (see his discussion of the helper function LargestV()).
Combinadics, unlike
factoradic s, does not appear to be anumeral system , although it has very much thelook and feel of one. In particular, it is different from amixed radix system.External links
* [http://msdn2.microsoft.com/en-us/library/aa289166(VS.71).aspx "Generating the mth Lexicographical Element of a Mathematical Combination", by James McCaffrey. Volt Information Sciences, Inc. July 2004 (a Visual C# .NET article from the MSDN Library)] Implementation of combinadics in C# source code
* [http://www-cs-faculty.stanford.edu/~knuth/fasc3a.ps.gz "The Art Of Computer Programming: Pre-Fascicle 3A, A DRAFT OF SECTION 7.2.1.3: GENERATING ALL COMBINATIONS" by Donald E. Knuth (compressed postscript file)] See pp 5-6 (of 11th revision) for a short discussion. Knuth has that Derrick Lehmer published the basictheorem in 1964, and an Ernesto Pascal described a "combinatorialnumber system " around 1887.
* [http://docs.google.com/Doc?id=ddd8c4hm_5fkdr3b A simple implementation of combinadics in Java by Michael J. Hudson]ee also
*
Factoradic
Wikimedia Foundation. 2010.
