List all 3-permutations of {1, 2, 3, 4, 5}.
The remaining exercises in this section develop another algorithm for generating the permutations of {1, 2, 3, . . . , n}. This algorithm is based on Cantor expansions of integers. Every nonnegative integer less than n! has a unique Cantor expansion
a11! + a22! +· · ·+ an−1(n − 1)!
where ai is a nonnegative integer not exceeding i, for i = 1, 2, . . . , n − 1. The integers a1, a2, . . . , an−1 are called the Cantor digits of this integer.
Given a permutation of {1, 2, . . . , n}, let ak−1, k = 2, 3, . . . , n, be the number of integers less than k that follow k in the permutation. For instance, in the permutation 43215, a1 is the number of integers less than 2 that follow 2, so a1 = 1. Similarly, for this example a2 = 2, a3 = 3, and a4 = 0. Consider the function from the set of permutations of {1, 2, 3, . . . , n} to the set of nonnegative integers less than n! that sends a permutation to the integer that has a1, a2, . . . , an−1, defined in this way, as its Cantor digits.