C# Fisher Yates ShuffleImplement the Fisher-Yates shuffle algorithm to randomize elements in arrays.
dot net perls
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.
Method notes. This is an accurate, effective shuffling method for all array types. Not only this, but this implementation of Shuffle() is fast and does not require any allocation.
Shuffle Array
Example program. This Shuffle implementation relies on the generic method syntax in the C# language. An instance of the Random type is also allocated and stored in a static field.
Generic Class, Method
In Main We use the Shuffle(T) method on integers and strings. It is equally effective on all types.
Shuffle, max We use the maximum bound of the loop of "n-1" as the last index does not need to touched in the loop—it is already shuffled.
Results The Shuffle method rearranged the 9-element int array, and the 3-element string array, so they are not in their original orders.
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 - 1); 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); Console.WriteLine("SHUFFLE: {0}", string.Join(",", array)); string[] array2 = { "bird", "frog", "cat" }; Shuffle(array2); Console.WriteLine("SHUFFLE: {0}", string.Join(",", array2)); } }
SHUFFLE: 3,5,7,8,6,9,1,2,4 SHUFFLE: cat,frog,bird
Notes, correctness. Some Shuffle methods have serious problems. They return incorrect results because they remove elements as they go along. There is a bias to the results.
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, and Peter Minarik, for pointing out flaws in previous versions of the code here.
A 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.
Fisher-Yates shuffle: Wikipedia
So The implementation may have been wrong. Currently the method is based on code from a CS textbook used at Princeton University.
An alternative. An alternative version of Shuffle() allocates a separate list and then assigns every element a random number key. It sorts based on that random number.
A 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. The implementation here has been tested and analyzed to ensure it is relatively free of problems.
© 2007-2021 sam allen. send bug reports to info@dotnetperls.com.