Constructing the kth Permutation 447As a result of examining the dictionary ordering of the permutations of three and
four elements, a predictable pattern is found for determining which element occurs at each
position in the permutation. For the case of four elements, observe that I is the first element
of the first 3! = 6 permutations, 2 is the first element of the second 3! = 6 permutations,
3 is the first element of the next 3! = 6 permutations, and finally, 4 is the first element
of the last 3! = 6 permutations. Now, observe the pattern of occurrence of the elements
in the second position. For example, the pattern in the second elements following the six
occurrences of 2 in the first position has each of the remaining elements repeated 2! times.
The element 1 occurs as the second element in the first 2! = 2 of these permutations, 3
occurs as the second element in the next 2! = 2 of these permutations, and finally, 4 occurs
as the second element in the last 2! = 2 of these permutations. The elements occurring in
the second position occur in increasing order. The next observation is that the two elements
that follow 2-3 in permutations 8 and 9, for example, are the elements 1 occurring 1! times
and then 4 occurring 1! times. Again, the elements that did not occur in earlier positions
occur in increasing order with frequency 1!.
In any sequence of (n - 1)! permutations with the same element in all the first posi-
tions, the second positions will have (n - 2)! occurrences of the smallest element not in
position 1, followed by (n - 2)! occurrences of the next smallest element not in position
1, and so on, for each of the n - 1 elements not in position 1. Similarly, in any sequence
of (n - 2)! permutations in which the elements in positions 1 and 2 do not change, the
third position will have (n - 3)! occurrences of the smallest element not in positions 1 or
2, followed by (n - 3)! occurrences of the next smallest element not in positions 1 or 2,
and so on. Any sequence of (n - k)! permutations for which the elements in positions 1
through k do not change begins with a permutation whose (k + 1)-st position is occupied
by the smallest element not in positions 1 through k.
A procedure for generating a particular permutation element by element is straightfor-
ward to implement using these ideas-provided that divisions by (n - 1)!, (n - 2)!. 2!
can be done. The next example illustrates the process.
Example 1. Find the 79th permutation of the elements 1, 2, 3, 4, and 5 relative to the
lexicographical order.
Solution. There are 120 permutations of five elements. Imagine ordering them in lexico-
graphical order and then numbering them from 0 to 119. Permutations 0 to 23 begin with
1, permutations 24 to 47 with 2, permutations 48 to 71 with 3, and permutations 72 to 95
with 4. Consequently, the first element of the 79th permutation is 4. To find the second
element of the permutation, imagine decomposing permutations 72 to 95 into sets of six
permutations. Permutations 72 to 77 have 1 as a second element, and permutations^78 to
83 have 2 as a second element. Therefore, the second element of the 79th permutation is 2.
To find the third element of the permutation, imagine decomposing permutations 78
to 83 into three sets of two permutations. Permutations 78 and 79 have 1 as the third
element. Thus, the third element of the 79th permutation is 1. The two elements 3 and
5 are in the fourth position in the 78th and 79th permutation following the 1 in the third
position of these permutations. Since we are constructing permutation 79, the next element
is 5. Finally, the only element not yet found is 3, and that occurs in position 5 of the 79th
permutation.
Therefore, the 79th permutation of 1, 2, 3, 4, and 5 relative to the lexicographical order
is 4-2-1-5-3. U