21. Consider the following algorithm for generating a random permutation of the elements 1, 2, . . . , n. In this algorithm, P(i) can be interpreted as the element in position i.

Step 1: Set k = 1.
Step 2: Set P(1) = 1.
Step 3: If k = n, stop. Otherwise, let k = k + 1.
Step 4: Generate a random number U, and let P(k) = P([kU] + 1), P([kU] + 1) = k.
Go to step 3.

(a) Explain in words what the algorithm is doing.

(b) Show that at iteration k—that is, when the value of P(k) is initially set—that P(1), P(2), . . . , P(k) is a random permutation of 1, 2, . . . , k.
Hint: Use induction and argue that Pk{i1, i2, . . . , ij−1, k, ij , . . . , ik−2, i}
= Pk−1{i1, i2, . . . , ij−1, i, ij , . . . , ik−2}1 k = 1 k! by the induction hypothesis The preceding algorithm can be used even if n is not initially known.