Categories
c# generic-list

Randomize a List

1048

What is the best way to randomize the order of a generic list in C#? I’ve got a finite set of 75 numbers in a list I would like to assign a random order to, in order to draw them for a lottery type application.

8

  • 4

    There is an open issue to integrate this functionality to .NET: github.com/dotnet/corefx/issues/461

    – Natan

    Mar 7, 2015 at 10:19

  • 7

    You may be interested in this NuGet package, which contains extension methods for shuffling IList<T> and IEnumerable<T> using the Fisher-Yates algorithm mentioned below

    May 7, 2016 at 14:44

  • 5

    @Natan they closed the issue because someone “worked on many projects and developed many libraries and never had a need in such a method” that pissed me off. Now we have to investigate ourselves, search for the best implementations, waste time to simply reinvent the wheel.

    Jul 16, 2019 at 11:56

  • 3

    Am I seeing this right? Not a single valid functional answer after 10 years ? Maybe we need another bounty for a solution which addresses the amount of entropy needed, to shuffle a list with 75 numbers $log2(75!) = 364$ and how we can get this. One would need to reseed even a cryptographically secure RNG with 256 bits of entropy at least once during a fisher-yates shuffle.

    – Falco

    Aug 1, 2019 at 16:39

  • 2

    And if the usual coder cannot solve this problem, have we all been playing the same 0.01% of possible solitaire games forever?

    – Falco

    Aug 1, 2019 at 16:41

1334

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;
      }
    }
  }
}

34

  • 36

    What if list.Count is > Byte.MaxValue? If n = 1000, then 255 / 1000 = 0, so the do loop will be an infinite loop since box[0] < 0 is always false.

    – AndrewS

    Jun 7, 2011 at 10:47

  • 19

    I would like to point out, that the comparison is flawed. Using <code>new Random()</code> in a loop is the problem, not the randomness of <code>Random</code> Explanation

    – Sven

    Sep 29, 2011 at 13:43

  • 9

    It is a good idea to pass an instance of Random to the Shuffle method rather than create it inside as if you are calling Shuffle lots of times in quick succession (e.g. shuffling lots of short lists), the lists will all be shuffled in the same way (e.g. first item always gets moved to position 3).

    Feb 7, 2012 at 22:43

  • 8

    Just making Random rng = new Random(); a static would solve the problem in the comparison post. As each subsequent call would follow on from the previous calls last random result.

    – weston

    Nov 28, 2012 at 13:58

  • 6

    #2, it’s not clear that the version with the Crypto generator works because the max range of a byte is 255, so any list larger than that will not shuffle correctly.

    May 8, 2013 at 14:37

461

If we only need to shuffle items in a completely random order (just to mix the items in a list), I prefer this simple yet effective code that orders items by guid…

var shuffledcards = cards.OrderBy(a => Guid.NewGuid()).ToList();

As people have pointed out in the comments, GUIDs are not guaranteed to be random, so we should be using a real random number generator instead:

private static Random rng = new Random();
...
var shuffledcards = cards.OrderBy(a => rng.Next()).ToList();

20

  • 49

    GUIDs are meant to be unique not random. Part of it is machine-based and another part time-based and only a small portion is random. blogs.msdn.com/b/oldnewthing/archive/2008/06/27/8659071.aspx

    – Despertar

    May 5, 2013 at 7:00

  • 121

    This is a nice elegant solution. If you want something other than a guid to generate randomness, just order by something else. Eg: var shuffledcards = cards.OrderBy(a => rng.Next()); compilr.com/grenade/sandbox/Program.cs

    – grenade

    May 27, 2013 at 10:54


  • 25

    Please no. This is wrong. “ordering by random” is totally NOT a shuffle: you introduce a bias and, worse, you risk to go in infinite loops

    Aug 16, 2013 at 10:07

  • 89

    @VitoDeTullio: You are misremembering. You risk infinite loops when you provide a random comparison function; a comparison function is required to produce a consistent total order. A random key is fine. This suggestion is wrong because guids are not guaranteed to be random, not because the technique of sorting by a random key is wrong.

    Sep 13, 2013 at 21:30

  • 30

    @Doug: NewGuid only guarantees that it gives you a unique GUID. It makes no guarantees about randomness. If you’re using a GUID for a purpose other than creating a unique value, you’re doing it wrong.

    Sep 13, 2013 at 21:31

127

I’m bit surprised by all the clunky versions of this simple algorithm here. Fisher-Yates (or Knuth shuffle) is bit tricky but very compact. Why is it tricky? Because your need to pay attention to whether your random number generator r(a,b) returns value where b is inclusive or exclusive. I’ve also edited Wikipedia description so people don’t blindly follow pseudocode there and create hard to detect bugs. For .Net, Random.Next(a,b) returns number exclusive of b so without further ado, here’s how it can be implemented in C#/.Net:

public static void Shuffle<T>(this IList<T> list, Random rnd)
{
    for(var i=list.Count; i > 0; i--)
        list.Swap(0, rnd.Next(0, i));
}

public static void Swap<T>(this IList<T> list, int i, int j)
{
    var temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

Try this code.

4

  • 6

    This code does not work as expected. The last number is always 0 or list.Count-1.

    – Oneiros

    Jan 3, 2020 at 17:52

  • 2

    @ShitalShah The current code in your answer doesn’t give correct results, because it’s not a correct Fisher-Yates shuffle. It should be fixed, as well as the code in the link.

    – Trisibo

    Jul 13, 2020 at 18:37

  • 4

    This code is broken. If you used a list of strings for 3 letters, “A”, “B”, and “C”, CBA, and BCA would literally never occur using this function, because of this line: list.Swap(0, rnd.Next(0, i)); switching it to the following fixes it and makes it a working, non-biased pseudo-random function: list.Swap(i-1, rnd.Next(0, i));

    Aug 10, 2020 at 12:21


  • 3

    OP: “Fischer-Yates is a bit tricky.” Proceeds to make one of the many common implementation mistakes.

    – D0SBoots

    Feb 13 at 6:10