Shuffle

Shuffling an array randomly reorders all elements, with results that are mathematically correct. Some solutions exist but do not give high-quality random results.

Imagine an array—we generate an array of completely random numbers of the same size. Then we sort the original array based on the values in the random number array.

Example code

Here we see an approach to shuffling a string array that is not an optimized shuffle. But it is mathematically random. It will not cause strange biases in your code.

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static Random _random = new Random();

    static string[] RandomizeStrings(string[] arr)
    {
        List<KeyValuePair<int, string>> list = new List<KeyValuePair<int, string>>();
        // Add all strings from array.
        // ... Add new random int each time.
        foreach (string s in arr)
        {
            list.Add(new KeyValuePair<int, string>(_random.Next(), s));
        }
        // Sort the list by the random number.
        var sorted = from item in list
                     orderby item.Key
                     select item;
        // Allocate new string array.
        string[] result = new string[arr.Length];
        // Copy values to array.
        int index = 0;
        foreach (KeyValuePair<int, string> pair in sorted)
        {
            result[index] = pair.Value;
            index++;
        }
        // Return copied array.
        return result;
    }

    static void Main()
    {
        string[] arr = new string[]
        {
            "cat",
            "dog",
            "bird",
            "ant"
        };
        string[] shuffle = RandomizeStrings(arr);
        foreach (string s in shuffle)
        {
            Console.WriteLine(s);
        }
    }
}
ant
cat
dog
bird

Fisher-yates shuffle

This is a more efficient version of array shuffling, named Fisher-Yates. It uses the C# generic method syntax. An instance of the Random type is stored in a static field.

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

We used a mathematically sound approach for shuffling an array. This method is not optimally fast. If you need performance, use an implementation of Fisher-Yates.