284
Sets, Combinatorics, and Probability
permutations of any n distinct elements; simply assign each of the n elements a
unique integer from 1 to n, generate the permutations of the integers, and then
reverse the assignment.
Our second problem is to generate the C(n, r) combinations of r distinct integers chosen from {1, … , n}. Such a combination does not involve order, it is
merely a subset of r elements. Nonetheless we will represent the subset {3, 5, 7}
as the sequence 357, and generate the subsets in lexicographical order. Once we
generate 357, we can’t also generate 375 or 753 or any of the other permutations of
the elements in this set. Each legitimate representation is an increasing sequence.
example 62
Consider the lexicographical ordering of the combinations of 4 integers from
{1, … , 7}. If the combination
2346
has just been generated, then the next combination would be
2347
obtained by incrementing the last digit of the sequence. However, in 2347, the last
digit is already at its maximum allowable value. Moving to the left, the 4 can be
bumped up to 5, but then the last digit has to be reduced to its minimum value,
which is 6 (one more than 5). Therefore,
2356
is the next combination. The next two values are
2357, 2367
at which point both 7 and 6 are at their maximum values. The 3 can be bumped up,
but the two digits to its right have to be reset to their lowest possible values. The
next few values are
2456, 2457, 2467, 2567 …
Based on the ideas of Example 62, given a combination sequence the algorithm should bump up the rightmost digit that is not at its maximum allowable
value. The sequence of digits to the right of the newly incremented digit v should
have the values v + 1, v + 2, and so on. The initial (smallest) combination is
12 … r.
Sets, Combinatorics, and Probability
permutations of any n distinct elements; simply assign each of the n elements a
unique integer from 1 to n, generate the permutations of the integers, and then
reverse the assignment.
Our second problem is to generate the C(n, r) combinations of r distinct integers chosen from {1, … , n}. Such a combination does not involve order, it is
merely a subset of r elements. Nonetheless we will represent the subset {3, 5, 7}
as the sequence 357, and generate the subsets in lexicographical order. Once we
generate 357, we can’t also generate 375 or 753 or any of the other permutations of
the elements in this set. Each legitimate representation is an increasing sequence.
example 62
Consider the lexicographical ordering of the combinations of 4 integers from
{1, … , 7}. If the combination
2346
has just been generated, then the next combination would be
2347
obtained by incrementing the last digit of the sequence. However, in 2347, the last
digit is already at its maximum allowable value. Moving to the left, the 4 can be
bumped up to 5, but then the last digit has to be reduced to its minimum value,
which is 6 (one more than 5). Therefore,
2356
is the next combination. The next two values are
2357, 2367
at which point both 7 and 6 are at their maximum values. The 3 can be bumped up,
but the two digits to its right have to be reset to their lowest possible values. The
next few values are
2456, 2457, 2467, 2567 …
Based on the ideas of Example 62, given a combination sequence the algorithm should bump up the rightmost digit that is not at its maximum allowable
value. The sequence of digits to the right of the newly incremented digit v should
have the values v + 1, v + 2, and so on. The initial (smallest) combination is
12 … r.