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]

n = length[A]
for i =0 ... n-1
do swap (A[i], A[RANDOM(i, n)])

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.