Suggest a Book

# Linear time shuffling

Level: unknown

posted Jul 21 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

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.

Source: folklore
delete retag edit

I would replace the first line with "for i = 0 to n-1". Yes, 0.

(Jul 21 '12)edit

@JeffE Thanks for pointing that out.

(Jul 21 '12)edit

## Stats

Posted: Jul 21 '12

Seen: 103 times

Last updated: Jul 21 '12