Consider the following algorithm to shuffle an array $A$ of $n$ elements (with indices from $0$ to $n-1$ :
for $i = 0$ to $n - 1$
Let j be a random integer between 0 and i exchange A[j] and A[i]
Prove that the above algorithm shuffles the array $A$ uniformly i.e., each of the $n!$ permutations are equally likely.
Posted: Jul 21 '12
Seen: 103 times
Last updated: Jul 21 '12
I would replace the first line with "for i = 0 to n-1". Yes, 0.
JeffE (Jul 21 '12)edit@JeffE Thanks for pointing that out.
Shiva Kintali (Jul 21 '12)edit