Tuesday, March 30, 2010

Random in place

Can you prove that the below code produces a random permutation, where RANDOM(i, n) produces a random integer in (i, n]

RANDOMIZE-IN-PLACE(A)
n = length[A]
for i =0 ... n-1
do swap (A[i], A[RANDOM(i, n)])
Pubblicato da a
Reazioni: 

1 comment:

  1. Generating random permutation is equivalent to repeated selection of a random number from 1 to n without replacement. This is what the code is doing precisely.

    ReplyDelete

Subscribe to: Post Comments (Atom)