282
Sets, Combinatorics, and Probability
which is the next permutation in the list. That’s all that can be done with the last
two digits; in particular, since 54 is a decreasing sequence, we can’t use these two
values to generate anything larger.
For the next number, we keep 12 − − − and consider how to arrange the last
three digits. Reading 12354 from right to left, we find in the last three digits that
3 < 5, but we know that everything from 5 to the right is a decreasing sequence.
The next permutation should replace 3 with the next largest value to its right.
Reading from right to left in the number 12354, the first value larger than 3, in
this case 4, is the least value larger than 3. Swapping 3 and 4 gives 12453, which
puts 4 in the correct order; the digits to the right are now in descending order, so
reversing them gives
12435
which is the next permutation.
example 61
To continue Example 60, let’s jump ahead. Suppose we have just generated
permutation
25431
and we want the next permutation. Reading from right to left, everything increases
until we get to 2, where we have 2 < 5. Starting again from right to left, we stop
at the first (and smallest) value greater than 2, which is 3. Swapping 2 and 3 gives
35421, giving the correct first digit. The digits after 3 are in descending order, so
reversing them involves swapping 5 and 1, and also swapping 4 and 2, giving the
next permutation
31245
algoRitHm Permutation Generator
PermGenerator(integer n ≥ 2)
//generates in lexicographical order all permutations
//of the integers in the set {1, …, n}
Local variables:
integers i, j
//indices of permutation elements
integer k
//for loop counter
integers d 1 , d 2 , …, d n
//left to right elements of a permutation
From the preceding examples, we can construct an algorithm to generate all
permutations of the integers from 1 to n in lexicographical order.