FisherYates Shuffle Algorithm
My blog is now located at http://www.WhoIsSethLong.com
I went to an interview recently and was asked to arrange an array of integers from 1 to 52 in random order. As soon as they said 52 I thought about a deck of cards, then instantly thought about the FisherYates Shuffle Algorithm.
The FisherYates Shuffle Algorithm is a simple algorithm that runs in linear time and is used to shuffle an array in random order. The algorithm loops through each item in the array, generates a random number between 0 and the array length, then assigns the array item to the randomly generated array position. This is a simple algorithm and is probably easiest understood with an example. For this example I’ll use C#.
public void FisherYates(int[] ary) { Random rnd = new Random(); for (int i = ary.Length  1; i > 0; i) { int r = rnd.Next(0, i); int tmp = ary[i]; ary[i] = ary[r]; ary[r] = tmp; } }
There are other ways to sort the array besides the Fisher Yates method. If this had been a deck of cards, another method would be to assign a randomly generated 64bit number to each card then sort by their randomly assigned number.
– Seth Long
3 Comments »
Leave a Reply

Archives
 May 2008 (1)
 February 2008 (3)
 January 2008 (6)

Categories

RSS
Entries RSS
Comments RSS
Hi
Although that your code is valid for most practical purpose, I’m afraid that the algorithm is not a correct FisherYates shuffle implementation. There should be N! possible permutation (instead of N^N produced by your code) from which one of permutation will be chosen.
Consider using this code :
for (int i = ary.Length – 1; i >= 0; i++)
{
int r = rnd.Next(0, i + 1);
int tmp = ary[i];
ary[i] = ary[r];
ary[r] = tmp;
}
Comment by monn  December 5, 2008 
Thank you for alerting me to the error. I guess it’s a fairly common mistake to make and a very serious one. Here is a link with more information on the error should anyone else need an explanation of how the error was made.
Good Knuth, Bad Knuth
Comment by Seth Long  December 11, 2008 
Of course, there should be “i–” in the loop, not “i++”.
Comment by Branko Dimitrijevic  August 6, 2010 