2. Another method of generating a random permutation, different from the one given in Example 15.2.b, 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.