Most Efficient Way to Randomly "Sort" (Shuffle) a List of Integers in C#

Most efficient way to randomly sort (Shuffle) a list of integers in C#

A good linear-time shuffling algorithm is the Fisher-Yates shuffle.

One problem you'll find with your proposed algorithm is that as you near the end of the shuffle, your loop will spend a lot of time looking for randomly chosen elements that have not yet been swapped. This may take an indeterminate amount of time once it gets to the last element to swap.

Also, it looks like your algorithm will never terminate if there are an odd number of elements to sort.

Randomize a List T

Shuffle any (I)List with an extension method based on the Fisher-Yates shuffle:

private static Random rng = new Random();  

public static void Shuffle<T>(this IList<T> list)  
{  
    int n = list.Count;  
    while (n > 1) {  
        n--;  
        int k = rng.Next(n + 1);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }  
}

Usage:

List<Product> products = GetProducts();
products.Shuffle();

The code above uses the much criticised System.Random method to select swap candidates. It's fast but not as random as it should be. If you need a better quality of randomness in your shuffles use the random number generator in System.Security.Cryptography like so:

using System.Security.Cryptography;
...
public static void Shuffle<T>(this IList<T> list)
{
    RNGCryptoServiceProvider provider = new RNGCryptoServiceProvider();
    int n = list.Count;
    while (n > 1)
    {
        byte[] box = new byte[1];
        do provider.GetBytes(box);
        while (!(box[0] < n * (Byte.MaxValue / n)));
        int k = (box[0] % n);
        n--;
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
    }
}

A simple comparison is available at this blog (WayBack Machine).

Edit: Since writing this answer a couple years back, many people have commented or written to me, to point out the big silly flaw in my comparison. They are of course right. There's nothing wrong with System.Random if it's used in the way it was intended. In my first example above, I instantiate the rng variable inside of the Shuffle method, which is asking for trouble if the method is going to be called repeatedly. Below is a fixed, full example based on a really useful comment received today from @weston here on SO.

Program.cs:

using System;
using System.Collections.Generic;
using System.Threading;

namespace SimpleLottery
{
  class Program
  {
    private static void Main(string[] args)
    {
      var numbers = new List<int>(Enumerable.Range(1, 75));
      numbers.Shuffle();
      Console.WriteLine("The winning numbers are: {0}", string.Join(",  ", numbers.GetRange(0, 5)));
    }
  }

  public static class ThreadSafeRandom
  {
      [ThreadStatic] private static Random Local;

      public static Random ThisThreadsRandom
      {
          get { return Local ?? (Local = new Random(unchecked(Environment.TickCount * 31 + Thread.CurrentThread.ManagedThreadId))); }
      }
  }

  static class MyExtensions
  {
    public static void Shuffle<T>(this IList<T> list)
    {
      int n = list.Count;
      while (n > 1)
      {
        n--;
        int k = ThreadSafeRandom.ThisThreadsRandom.Next(n + 1);
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
      }
    }
  }
}

Simple way to randomly shuffle list

Try this (based on Fisher–Yates shuffle algorithm)

public static void ShuffleMe<T>(this IList<T> list)  
{  
    Random random = new Random();  
    int n = list.Count;  

    for(int i= list.Count - 1; i > 1; i--)
    {
        int rnd = random.Next(i + 1);  

        T value = list[rnd];  
        list[rnd] = list[i];  
        list[i] = value;
    }
}

List<Color> colors = new List<Color> ();
colors.Add(Color.Black);
colors.Add(Color.White);
colors.Add(Color.Red);

colors.ShuffleMe();

Sort list in random number order

The first one is just badness. GUIDs are unique, but they are not necessarily random. While some GUID implementations may rely on randomness, others won't. The result here is that the exact same program run on one machine will work and on another won't. That's really bad as it means you'll test your program, it will come out fine, you'll ship it, and things will break.

The third is a pretty standard shuffling algorithm. It's generally what I'd go with when solving this problem.

The second option will work, but it's noticeably less efficient than the third option. Sorting has a higher asymptotic complexity than the third algorithm you've shown there (O(n*log(n)) instead of O(n)).

If you had to write the code every single time you wanted to use it there may be value in the method that's 2 lines instead of a dozen, but when you only need to write it once and simply reference that general purpose shuffle method any time you need to shuffle a sequence you can justify using the semantically proper and more efficient code. (After all it's not that long or complex.)

shuffle (rearrange randomly) a List string

List<Foo> source = ...
var rnd = new Random();
var result = source.OrderBy(item => rnd.Next());

Obviously if you want real randomness instead of pseudo-random number generator you could use RNGCryptoServiceProvider instead of Random.

Is using Random and OrderBy a good shuffle algorithm?

It's not a way of shuffling that I like, mostly on the grounds that it's O(n log n) for no good reason when it's easy to implement an O(n) shuffle. The code in the question "works" by basically giving a random (hopefully unique!) number to each element, then ordering the elements according to that number.

I prefer Durstenfeld's variant of the Fisher-Yates shuffle which swaps elements.

Implementing a simple Shuffle extension method would basically consist of calling ToList or ToArray on the input then using an existing implementation of Fisher-Yates. (Pass in the Random as a parameter to make life generally nicer.) There are plenty of implementations around... I've probably got one in an answer somewhere.

The nice thing about such an extension method is that it would then be very clear to the reader what you're actually trying to do.

EDIT: Here's a simple implementation (no error checking!):

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length-1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        T tmp = elements[i];
        elements[i] = elements[swapIndex];
        elements[swapIndex] = tmp;
    }
    // Lazily yield (avoiding aliasing issues etc)
    foreach (T element in elements)
    {
        yield return element;
    }
}

EDIT: Comments on performance below reminded me that we can actually return the elements as we shuffle them:

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    for (int i = elements.Length - 1; i >= 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        // ... except we don't really need to swap it fully, as we can
        // return it immediately, and afterwards it's irrelevant.
        int swapIndex = rng.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}

This will now only do as much work as it needs to.

Note that in both cases, you need to be careful about the instance of Random you use as:

• Creating two instances of Random at roughly the same time will yield the same sequence of random numbers (when used in the same way)
• Random isn't thread-safe.

I have an article on Random which goes into more detail on these issues and provides solutions.

Shuffle Numbers and Generate Same Sequence of Numbers in every Execution

It is more efficient to use an algorithm like Fisher-Yates shuffle to reorder the items. The run-time complexity of OrderBy is O(N log N) while Fisher-Yates shuffle is O(N).

Also, to provide random numbers you should use the Random class, not Guid.NewGuid which serves a completely different purpose and just happens to create something that is random (at a higher cost).

I prefer to implement the shuffle as an extension method:

public static class ListExtensions
{
    public static IList<T> Shuffle<T>(this IList<T> list, Random random)
    {
        for (var i = list.Count; i > 1; i -= 1)
        {
            var j = random.Next(i); 
            var temp = list[j];
            list[j] = list[i - 1];
            list[i - 1] = temp;
        }
        return list;
    }
}

You can achieve the desired result by providing a Random instance with a specific seed (in this case 0). This will ensure that the sequence of random numbers generated are the same each time the code executes:

var shuffledList = Enumerable.Range(0, 1000).ToList().Shuffle(new Random(0));

Randomize a list but with range

It's very easy to adapt a standard random shuffle algorithm to accept a starting index and a count:

public static void Shuffle<T>(IList<T> array, Random rng, int first, int count)
{
    for (int n = count; n > 1;)
    {
        int k = rng.Next(n);
        --n;
        T temp = array[n+first];
        array[n + first] = array[k + first];
        array[k + first] = temp;
    }
}

Then if you want to shuffle all but the first and the last items:

Shuffle(items, new Random(), 1, items.Count-2);

---

Related Topics