Page 459 - Discrete Mathematics and Its Applications

438 6 / Counting

Algorithm 3 displays pseudocode for this procedure.

ALGORITHM 3 Generating the Next r-Combination in Lexicographic Order.

procedure next r-combination({a 1 ,a 2 ,...,a r }: proper subset of
{1, 2,...,n} not equal to {n − r + 1,...,n} with
a 1 <a 2 < ··· <a r )
i := r
while a i = n − r + i
i := i − 1
a i := a i + 1
for j := i + 1 to r
a j := a i + j − i
{{a 1 ,a 2 ,...,a r } is now the next combination}

Exercises

1. Place these permutations of {1, 2, 3, 4, 5} in lexico- 10. Show that Algorithm 1 produces the next larger permu-
graphic order: 43521, 15432, 45321, 23451, 23514, tation in lexicographic order.
14532, 21345, 45213, 31452, 31542. 11. Show that Algorithm 3 produces the next larger
2. Place these permutations of {1,2,3,4,5,6} in lexico- r-combination in lexicographic order after a given
graphicorder:234561,231456,165432,156423,543216, r-combination.
541236, 231465, 314562, 432561, 654321, 654312, 12. Develop an algorithm for generating the r-permutations
435612. of a set of n elements.
3. The name of a file in a computer directory consists of 13. List all 3-permutations of {1, 2, 3, 4, 5}.
three uppercase letters followed by a digit, where each The remaining exercises in this section develop another algo-
letter is either A, B, or C, and each digit is either 1 or 2. rithm for generating the permutations of {1, 2, 3,...,n}. This
List the name of these files in lexicographic order, where algorithm is based on Cantor expansions of integers. Every
we order letters using the usual alphabetic order of letters. nonnegative integer less than n! has a unique Cantor expan-
sion
4. Suppose that the name of a file in a computer directory
consists of three digits followed by two lowercase letters a 1 1!+ a 2 2! + ··· + a n−1 (n − 1)!
and each digit is 0, 1, or 2, and each letter is either a or b. where a i is a nonnegative integer not exceeding i, for i =
List the name of these files in lexicographic order, where 1, 2,...,n − 1. The integers a 1 ,a 2 ,...,a n−1 are called the
we order letters using the usual alphabetic order of letters. Cantor digits of this integer.
5. Find the next larger permutation in lexicographic order Given a permutation of {1, 2,...,n}, let a k−1 ,k =
after each of these permutations. 2, 3,...,n, be the number of integers less than k that fol-
a) 1432 b) 54123 c) 12453 low k in the permutation. For instance, in the permutation
43215, a 1 is the number of integers less than 2 that fol-
d) 45231 e) 6714235 f) 31528764
low2,so a 1 = 1. Similarly, for this example a 2 = 2, a 3 = 3,
6. Find the next larger permutation in lexicographic order and a 4 = 0. Consider the function from the set of permu-
after each of these permutations. tations of {1, 2, 3,...,n} to the set of nonnegative integers
a) 1342 b) 45321 c) 13245 less than n! that sends a permutation to the integer that has
a 1 ,a 2 ,...,a n−1 , defined in this way, as its Cantor digits.
d) 612345 e) 1623547 f) 23587416
7. Use Algorithm 1 to generate the 24 permutations of the 14. Find the Cantor digits a 1 ,a 2 ,...,a n−1 that correspond
first four positive integers in lexicographic order. to these permutations.
a) 246531 b) 12345 c) 654321
8. UseAlgorithm2tolistallthesubsetsoftheset{1, 2, 3, 4}.
∗ 15. Show that the correspondence described in the pream-
9. Use Algorithm 3 to list all the 3-combinations of ble is a bijection between the set of permutations of
{1, 2, 3, 4, 5}. {1, 2, 3,...,n} and the nonnegative integers less than n!.