随机化 List <T>

在 C＃中随机化通用列表顺序的最佳方法是什么？我在一个列表中有一组有限的 75 个数字，我想为其分配一个随机顺序，以便为抽奖类型的应用程序绘制它们。

答案

使用基于Fisher-Yates shuffle的扩展方法随机播放任何(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;  
    }  
}

用法：

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

上面的代码使用备受批评的 System.Random 方法来选择交换候选。它很快但不是随意的。如果你需要在 shuffle 中使用更好的随机性质，请使用 System.Security.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;
    }
}

这个博客（WayBack Machine）提供了一个简单的比较。

编辑：自从几年前写这个答案以来，很多人都评论或写信给我，指出我比较中的一个很大的愚蠢缺陷。他们当然是对的。 System.Random 没有任何问题，如果按照预期的方式使用它。在我上面的第一个例子中，我在 Shuffle 方法中实例化了 rng 变量，如果要重复调用该方法，则会遇到麻烦。下面是一个固定的完整示例，基于今天从 @weston 收到的关于 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();

我对这个简单算法的所有笨重版本感到有些惊讶。 Fisher-Yates（或 Knuth shuffle）有点棘手但非常紧凑。如果你去维基百科，你会看到这个算法的版本反向循环，很多人似乎并不真正理解为什么它会反过来。关键原因是这个版本的算法假定随机数生成器Random(n)具有以下两个属性：

它接受 n 作为单个输入参数。
它从 0 返回数 n 以下。

但. Net 随机数生成器不满足＃2 属性。相反， Random.Next(n)返回从 0 到 n-1 的数字。如果您尝试反向使用 for 循环，则需要调用Random.Next(n+1) ，这会添加一个额外的操作。

但是，.Net 随机数生成器还有另一个很好的函数Random.Next(a,b) ，它返回 a 到 b-1。这实际上非常适合具有正常 for 循环的该算法的实现。所以，不用多说，这是正确，高效和紧凑的实现：

public static void Shuffle<T>(this IList<T> list, Random rnd)
{
    for(var i=0; i < list.Count - 1; 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;
}