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. Not only this, but this implementation of Shuffle() is fast and does not require any allocation.

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.Random Static 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)); } } Output 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.Shuffle Array

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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# Fisher Yates Shuffle: Generic Method

Related Links:

.Net

Java

Related Links