Fisher-Yates 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 Fisher-Yates Shuffle Algorithm.

The Fisher-Yates 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 64-bit number to each card then sort by their randomly assigned number.

- Seth Long

January 3, 2008 - Posted by Seth Long | Algorithms | | 2 Comments

2 Comments »

Hi

Although that your code is valid for most practical purpose, I’m afraid that the algorithm is not a correct Fisher-Yates 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 | Reply
- 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 | Reply