C# Fisher-Yates Shuffle: Generic Method

Fisher-Yates shuffle. Shuffling an array randomizes its element order.

With the Fisher-Yates shuffle, first implemented on computers by Durstenfeld in 1964, we randomly sort elements. This is an accurate, effective shuffling method for all array types.

Example. First, this Shuffle implementation relies on the generic method syntax in the C# programming language. An instance of the Random type is also allocated and stored in a static field.

Static MethodGeneric MethodRandomStatic Field

Next: In the Main entry point, we use the Shuffle(T) method on integers and strings. It is equally effective on all types.

Based on:

.NET 4.5

C# program that implements generic Fisher-Yates shuffle

using System;

class Program
{
    /// <summary>
    /// Used in Shuffle(T).
    /// </summary>
    static Random _random = new Random();

    /// <summary>
    /// Shuffle the array.
    /// </summary>
    /// <typeparam name="T">Array element type.</typeparam>
    /// <param name="array">Array to shuffle.</param>
    static void Shuffle<T>(T[] array)
    {
	int n = array.Length;
	for (int i = 0; i < n; i++)
	{
	    // NextDouble returns a random number between 0 and 1.
	    // ... It is equivalent to Math.random() in Java.
	    int r = i + (int)(_random.NextDouble() * (n - i));
	    T t = array[r];
	    array[r] = array[i];
	    array[i] = t;
	}
    }

    static void Main()
    {
	{
	    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	    Shuffle(array);
	    foreach (int value in array)
	    {
		Console.WriteLine(value);
	    }
	}
	{
	    string[] array = { "dot", "net", "deves" };
	    Shuffle(array);
	    foreach (string value in array)
	    {
		Console.WriteLine(value);
	    }
	}
    }
}

Output

6
8
2
7
4
3
5
9
1
net
deves
dot

Results of the program. The Shuffle(T) method rearranged the nine-element integer array so it is not in its original order. The three-element string array was also randomly rearranged.

Int Array

Is it correct? Some Shuffle methods have an interesting problem. They return incorrect results because they remove elements as they go along. This means that there is a bias to the results. This can be proven through tests.

Princeton: This code the same as the Java shuffle algorithm from the Princeton computer science introductory course.

Arrays: Princeton.edu

Math.random: In Java, the Math.random method returns a double between 0 and 1. The NextDouble method in C# is equivalent.

Random, Java

Note: Thanks to Darrin Henning for pointing out that the previous algorithm was incorrect.

Discussion. Shuffle algorithms are hard to develop and test. Often biases can occur. Previously, I had based this code on a Java implementation from Wikipedia, but this was removed. The implementation may have been wrong.

Fisher-Yates shuffle: Wikipedia

So: Currently the method is based on that from a CS textbook used at Princeton University.

Also, there is a different implementation of Shuffle on this website. The version simply allocates a separate list and then assigns every element a random number key. It sorts based on that random number.

Shuffle Array

Caution: The linked implementation is likely much slower than Fisher-Yates in the C# language.

Summary. The Fisher-Yates shuffle algorithm, implemented in 1964 by Durstenfeld and described by Donald Knuth, is an efficient and correct way to sort arrays. It provides a useful, versatile shuffling routine.

Related Links