Problem
In C#, what is the best approach to shuffle the order of a generic list? I have a finite set of 75 numbers in a list that I’d like to assign a random order to so that they can be drawn in a lottery.
Asked by mirezus
Solution #1
With an extension approach based on the Fisher-Yates shuffle, you can shuffle any (I)List:
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 makes advantage of the widely panned System. To choose swap candidates, use a random technique. It’s quick, but not as unpredictable as it should be. If you want a higher level of randomization in your shuffles, use System’s random number generator. Security. As an example of cryptography:
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;
}
}
This blog provides a basic comparison (WayBack Machine).
Many people have posted or written to me since I wrote this answer a few years ago, pointing out the major fault in my comparison. Of course, they are correct. System is in perfect working order. If it’s used correctly, it’ll be random. I initialize the rng variable inside the Shuffle method in my first example, which is begging for trouble if the method is going to be called again. Below is a fixed, complete example based on a very helpful comment from @weston on SO today.
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;
}
}
}
}
Answered by grenade
Solution #2
I prefer this simple yet effective code that organizes items by guid if we only need to shuffle objects in a fully random order (only to mix the items in a list).
var shuffledcards = cards.OrderBy(a => Guid.NewGuid()).ToList();
GUIDs aren’t guaranteed to be random, as some have pointed out in the comments, thus we need use a true random number generator instead:
private static Random rng = new Random();
...
var shuffledcards = cards.OrderBy(a => rng.Next()).ToList();
Answered by user453230
Solution #3
I’m a little startled by the number of clumsy implementations of this simple technique here. Fisher-Yates (also known as the Knuth shuffle) is a challenging but compact shuffle. What makes it so difficult? Because you must determine whether your random number generator r(a,b) returns an inclusive or exclusive result. 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.
Answered by Shital Shah
Solution #4
IEnumerable extension method:
public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source)
{
Random rnd = new Random();
return source.OrderBy<T, int>((item) => rnd.Next());
}
Answered by Denis
Solution #5
The idea is to create an anonymous object with an item and a random order, then reorder the items according to that order and return the value:
var result = items.Select(x => new { value = x, order = rnd.Next() })
.OrderBy(x => x.order).Select(x => x.value).ToList()
Answered by Andrey Kucher
Post is based on https://stackoverflow.com/questions/273313/randomize-a-listt