Another method of generating a random permutation, different from the one given in Example 15.2b, is to successively generate a random permutation of the numbers 1, 2, . . . , n starting with n = 1, then n = 2, and so on. (Of course, the random permutation when n = 1 is 1.) Once we have a random permutation of the numbers 1, . . . , n − 1—call it P1, P2, . . . , Pn−1—the random permutation of the numbers 1, . . . , n is obtained by starting with the permutation P1, P2, . . . , Pn−1, n, then interchanging the element in position n (namely, n) with the element in a randomly chosen position that is equally likely to be any of the positions 1, 2, . . . , n.

(a) Write an algorithm that accomplishes the preceding.

(b) Verify when n = 2 and when n = 3 that all n! possible permutations are equally likely.