Section 4.4 Permutations and Combinations
283
//create and write out smallest permutation
for k = 1 to n do
d k = k
end for
write d 1 d 2 …d n
//create and write out remaining permutations
for k = 2 to n! do
//look right to left for first break in increasing sequence
i = n – 1
j = n
while d i > d j do //still increasing right to left
i = i – 1
j = j – 1
end while
//now d i < d j , need to replace d i with next largest integer
//look right to left for smallest value greater than d i
j = n
while d i > d j do
j = j – 1
end while
//now d j is smallest value > d i
swap d i and d j
//reverse the digits to the right of index i
i = i + 1
j = n
while i < j do
swap d i and d j
i = i + 1
j = j − 1
end while
write d 1 d 2 …d n
end for
end function PermGenerator
PraCtiCe 37 Walk through the steps in the algorithm that generate the next permutation following
51432.
■
Another algorithm for generating (not in lexicographical order) all permutations of the integers {1, … , n} is suggested in Exercise 7 of On the Computer at
the end of this chapter. Both of these algorithms can also be used to generate all