Page 456 - Discrete Mathematics and Its Applications

6.6 Generating Permutations and Combinations 435
Any set with n elements can be placed in one-to-one correspondence with the set {1, 2, 3,...,n}.
EXAMPLE 1
set of employees is to generate all sets of 12 of these employees and check whether they have
the desired skills. These examples show that it is often necessary to generate permutations and
combinations to solve problems.
Generating Permutations
We can list the permutations of any set of n elements by generating the permutations of the n
smallest positive integers and then replacing these integers with the corresponding elements.
Many different algorithms have been developed to generate the n! permutations of this set. We
will describe one of these that is based on the lexicographic (or dictionary) ordering of the set
of permutations of {1, 2, 3,...,n}. In this ordering, the permutation a 1 a 2 ··· a n precedes the
permutation of b 1 b 2 ··· b n , if for some k, with 1 ≤ k ≤ n, a 1 = b 1 , a 2 = b 2 ,..., a k−1 = b k−1 ,
and a k <b k . In other words, a permutation of the set of the n smallest positive integers precedes
(in lexicographic order) a second permutation if the number in this permutation in the first
position where the two permutations disagree is smaller than the number in that position in the
second permutation.
The permutation 23415 of the set {1, 2, 3, 4, 5} precedes the permutation 23514, because these
permutations agree in the first two positions, but the number in the third position in the first
permutation, 4, is smaller than the number in the third position in the second permutation, 5.
Similarly, the permutation 41532 precedes 52143. ▲
An algorithm for generating the permutations of {1, 2,...,n} can be based on a proce-
dure that constructs the next permutation in lexicographic order following a given permutation
a 1 a 2 ··· a n . We will show how this can be done. First, suppose that a n−1 <a n . Interchange a n−1
and a n to obtain a larger permutation. No other permutation is both larger than the original per-
mutation and smaller than the permutation obtained by interchanging a n−1 and a n . For instance,
the next larger permutation after 234156 is 234165. On the other hand, if a n−1 >a n , then a
larger permutation cannot be obtained by interchanging these last two terms in the permutation.
Look at the last three integers in the permutation. If a n−2 <a n−1 , then the last three integers in
the permutation can be rearranged to obtain the next largest permutation. Put the smaller of the
two integers a n−1 and a n that is greater than a n−2 in position n − 2. Then, place the remaining
integer and a n−2 into the last two positions in increasing order. For instance, the next larger
permutation after 234165 is 234516.
On the other hand, if a n−2 >a n−1 (and a n−1 >a n ), then a larger permutation cannot be
obtained by permuting the last three terms in the permutation. Based on these observations, a
general method can be described for producing the next larger permutation in increasing order
following a given permutation a 1 a 2 ··· a n . First, find the integers a j and a j+1 with a j <a j+1
and
a j+1 >a j+2 > ··· >a n ,
that is, the last pair of adjacent integers in the permutation where the first integer in the pair is
smaller than the second. Then, the next larger permutation in lexicographic order is obtained
by putting in the jth position the least integer among a j+1 ,a j+2 ,..., and a n that is greater
than a j and listing in increasing order the rest of the integers a j ,a j+1 ,...,a n in positions j + 1
to n. It is easy to see that there is no other permutation larger than the permutation a 1 a 2 ··· a n but
smaller than the new permutation produced. (The verification of this fact is left as an exercise
for the reader.)