Combinadic
From Wikipedia, the free encyclopedia
In mathematics, a combinadic is an ordered integer partition, or composition. Combinadics provide a lexicographical index for combinations. Applications for combinadics include software testing, sampling, quality control, and the analysis of gambling 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 ith k-combination taken from the set of n elements. Then the index for the ten 3-combinations of the set of five elements can be written out as follows.
ith 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 ith 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 ith combinadic in this system is defined to be the ordered n-tuple consisting of the letter positions for the 1s in the nth 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.
ith word
(places) ith 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 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 ith word
e Index Breakdown of Index (places) ith 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 ith combinadic M(n,k)(i) is the unique strictly decreasing sequence (mk−1, mk−2, ..., m0) of k integers lying between n − 1 and 0 so that C(mk−1,k) + C(mk−2,k − 1) + ... + C(m0,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 mk−1 so that C(mk−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(mk−1,k), n is set to the previous mk−1, and k is reduced by one. This is continued until k is reduced to zero. As McCaffrey points out in his MSN article, efficiently finding the largest mk−1 is the key to calculating a k-combination from its index value (see his discussion of the helper function LargestV()).
Combinadics, unlike factoradics, does not appear to be a numeral system, although it has very much the look and feel of one. In particular, it is different from a mixed radix system.
[edit] External links
- "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
- "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 basic theorem in 1964, and an Ernesto Pascal described a combinatorial number system around 1887.
