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