- Access to
**800,000+**Textbook Solutions - Ask any question from
**24/7**available

Tutors **Live Video**Consultation with Tutors**50,000+**Answers by Tutors

The following algorithm will generate a random permutation of the

The following algorithm will generate a random permutation of the elements 1, 2, . . . , n. It is somewhat faster than the one presented in Example 1a but is such that no position is fixed until the algorithm ends. 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—P(1), P(2), . . . , P(k) is a random permutation of 1, 2, . . . , k.

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

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—P(1), P(2), . . . , P(k) is a random permutation of 1, 2, . . . , k.

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

Membership
TRY NOW

- Access to
**800,000+**Textbook Solutions - Ask any question from
**24/7**available

Tutors **Live Video**Consultation with Tutors**50,000+**Answers by Tutors

Relevant Tutors available to help