Best way to randomize an array with .NET

by

The following implementation uses the Fisher-Yates algorithm AKA the Knuth Shuffle. It runs in O(n) time and shuffles in place, so is better performing than the ‘sort by random’ technique, although it is more lines of code. See here for some comparative performance measurements. I have used System.Random, which is fine for non-cryptographic purposes.*

static class RandomExtensions
{
    public static void Shuffle<T> (this Random rng, T[] array)
    {
        int n = array.Length;
        while (n > 1) 
        {
            int k = rng.Next(n--);
            T temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }
    }
}

Usage:

var array = new int[] {1, 2, 3, 4};
var rng = new Random();
rng.Shuffle(array);
rng.Shuffle(array); // different order from first call to Shuffle

* For longer arrays, in order to make the (extremely large) number of permutations equally probable it would be necessary to run a pseudo-random number generator (PRNG) through many iterations for each swap to produce enough entropy. For a 500-element array only a very small fraction of the possible 500! permutations will be possible to obtain using a PRNG. Nevertheless, the Fisher-Yates algorithm is unbiased and therefore the shuffle will be as good as the RNG you use.

More Related Contents:

  1. Best way to reverse a string
  2. Algorithm to detect overlapping periods [duplicate]
  3. Generating random, unique values C#
  4. Select N random elements from a List in C#
  5. What guarantees are there on the run-time complexity (Big-O) of LINQ methods?
  6. C# Point in polygon
  7. C# Sort and OrderBy comparison
  8. C# List Sort by x then y
  9. Produce a random number in a range using C#
  10. How do I sort an observable collection?
  11. Remove text in-between delimiters in a string (using a regex?)
  12. Generate N random and unique numbers within a range
  13. How Math.Pow (and so on) actually works
  14. Parallel Sort Algorithm
  15. Generating a Random Decimal in C#
  16. How to sort depended objects by dependency
  17. Split String into smaller Strings by length variable
  18. Compare string similarity
  19. Calculate median in c#
  20. C#: Seeking PNG Compression algorithm/library [closed]
  21. How to sort TreeView items using SortDescriptions in Xaml?
  22. Random slot algorithm
  23. Memory-constrained external sorting of strings, with duplicates combined&counted, on a critical server (billions of filenames)
  24. Pros and cons of RNGCryptoServiceProvider
  25. How can I tell if a point belongs to a certain line?
  26. Creating a power set of a Sequence
  27. All cases covered Bresenham’s line-algorithm [closed]
  28. How to get random values from array in C# [duplicate]
  29. Why does the default string comparer fail to maintain transitive consistency?
  30. How to round decimal value up to nearest 0.05 value?

Leave a Comment