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
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
OR
Relevant Tutors available to help