Tuesday, 8 July 2008

Unsorting.

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:
1,2,3,4
n = 4, r = rand(0,4) = 2
1,2,4,3
n = 3, r = rand(0,3) = 0
4,2,1,3
n = 2, r = rand(0,2) = 1
4,2,1,3
n = 1 (finish)

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