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.

## No comments:

Post a comment