Coding Notes

Ideas and thoughts from Seth Long

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

Advertisements

January 3, 2008 - Posted by | Algorithms

3 Comments »

  1. 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

  2. Of course, there should be “i–” in the loop, not “i++”.

    Comment by Branko Dimitrijevic | August 6, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: