Randomize a List<T>
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.
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;
}
}
}
}
如果我们只需要以完全随机的顺序对物品进行洗牌（只是为了混合列表中的物品），我更喜欢这个简单而有效的代码，通过guid来订购物品......
var shuffledcards = cards.OrderBy(a => Guid.NewGuid()).ToList();
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. If you go to Wikipedia, you would see a version of this algorithm that has for-loop in reverse and lot of people don't really seem to understand why is it in reverse. The key reason is that this version of algorithm assumes that the random number generator Random(n) at your disposal has following two properties:
However .Net random number generator does not satisfy #2 property. The Random.Next(n) instead returns number from 0 to n-1 inclusive. If you try to use for-loop in reverse then you would need to call Random.Next(n+1) which adds one additional operation.
However, .Net random number generator has another nice function Random.Next(a,b) which returns a to b-1 inclusive. This actually perfectly fits nicely with implementation of this algorithm that has normal for-loop. So without further ado, here's the correct, efficient and compact implementation:
public static void Shuffle<T>(this IList<T> list, Random rnd)
{
for(var i=0; i < list.Count; i++)
list.Swap(i, rnd.Next(i, list.Count));
}
public static void Swap<T>(this IList<T> list, int i, int j)
{
var temp = list[i];
list[i] = list[j];
list[j] = temp;
}
上一篇: LINQ表达式仅提取两个单词短语
下一篇: 随机化列表<T>