HomeSearch

C# Fisher Yates Shuffle: Generic Method

Implement the Fisher-Yates shuffle algorithm to randomize elements in arrays.
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.
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.RandomStaticGeneric Class, Method

In Main: We use the Shuffle(T) method on integers and strings. It is equally effective on all types.

Results: The Shuffle(T) method rearranged the nine-element integer array so it is not in its original order.

Also: The three-element string array was also randomly rearranged. The original elements are still present, but in different positions.

Int Array
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++) { // Use Next on random instance with an argument. // ... The argument is an exclusive bound. // So we will not go past the end of the array. int r = i + _random.Next(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", "perls" }; Shuffle(array); foreach (string value in array) { Console.WriteLine(value); } } } } Output 6 4 8 5 2 9 1 3 7 net perls dot
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.

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. 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.
© 2007-2019 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.
Home
Dot Net Perls