Page 457 - Discrete Mathematics and Its Applications

436 6 / Counting

EXAMPLE 2 What is the next permutation in lexicographic order after 362541?

Solution: The last pair of integers a j and a j+1 where a j <a j+1 is a 3 = 2 and a 4 = 5. The
least integer to the right of 2 that is greater than 2 in the permutation is a 5 = 4. Hence, 4 is
placed in the third position. Then the integers 2, 5, and 1 are placed in order in the last three
positions, giving 125 as the last three positions of the permutation. Hence, the next permutation
is 364125. ▲

To produce the n! permutations of the integers 1, 2, 3,...,n, begin with the smallest permu-
tation in lexicographic order, namely, 123 ··· n, and successively apply the procedure described
for producing the next larger permutation of n!− 1 times. This yields all the permutations of
the n smallest integers in lexicographic order.

EXAMPLE 3 Generate the permutations of the integers 1, 2, 3 in lexicographic order.

Solution: Begin with 123. The next permutation is obtained by interchanging 3 and 2 to obtain
132. Next, because 3 > 2 and 1 < 3, permute the three integers in 132. Put the smaller of 3
and 2 in the first position, and then put 1 and 3 in increasing order in positions 2 and 3 to
obtain 213. This is followed by 231, obtained by interchanging 1 and 3, because 1 < 3. The next
larger permutation has 3 in the first position, followed by 1 and 2 in increasing order, namely,
312. Finally, interchange 1 and 2 to obtain the last permutation, 321. We have generated the
permutations of 1, 2, 3 in lexicographic order. They are 123, 132, 213, 231, 312, and 321. ▲

Algorithm 1 displays the procedure for finding the next permutation in lexicographic order
after a permutation that is not nn − 1 n − 2 ... 2 1, which is the largest permutation.

ALGORITHM 1 Generating the Next Permutation in Lexicographic Order.

procedure next permutation(a 1 a 2 ...a n : permutation of
{1, 2,...,n} not equal to nn − 1 ... 21)
j := n − 1
while a j >a j+1
j := j − 1
{j is the largest subscript with a j <a j+1 }
k := n
while a j >a k
k := k − 1
{a k is the smallest integer greater than a j to the right of a j }
interchange a j and a k
r := n
s := j + 1
while r> s
interchange a r and a s
r := r − 1
s := s + 1
{this puts the tail end of the permutation after the jth position in increasing order}
{a 1 a 2 ...a n is now the next permutation}