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 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 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₀) of k integers lying between n − 1 and 0 so that C(m_k−1,k) + C(m_k−2,k − 1) + ... + C(m₀,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 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 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.