Tuesday, 8 July 2008


Something I learnt from Ian Gledhill:

If you have a list that you want to shuffle, you can do it very efficiently by using the following technique.

First, define N as the number of items in the list.
n = N
r is a random number between zero and n (not inlusive)
swap element r and element n-1
reduce n by one
if n is greater than 1, then return to the line where you make r at random.

consider the following list:
n = 4, r = rand(0,4) = 2
n = 3, r = rand(0,3) = 0
n = 2, r = rand(0,2) = 1
n = 1 (finish)

This is about as optimal a shuffle as is possible. It's even better that it's an in place operation.

No comments: