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

Step 1: Set k = 1.

Step 2: Set P(l) = 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(l), P(2), ...,P(k) is a random permutation of 1, 2 , k .

Hint: Use induction and argue that Pk\h » h > · · · » (/-1 > ^> ( / > · · · > 'Ar-2 >'}

= A:- ll'l » '2 >···>(/-1 > '> Ô » ' ' ' ' ^-2) ^

= ~Ã7 by the induction hypothesis A:!

The preceding algorithm can be used even if ç is not initially known.