随机化列表<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方法来选择交换候选项。 它速度很快，但不像应该那样随机。 如果你的洗牌需要更好的随机性质量，可以使用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收到的真正有用的评论。

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-loop，那么你需要调用Random.Next(n+1) ，这会增加一个额外的操作。

然而，.Net随机数生成器有另一个很好的函数Random.Next(a,b) ，它返回a到b-1（含）。 这实际上非常适合实现具有正常循环的算法。 所以，不用再做了，下面是正确，高效和紧凑的实现：

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

链接地址: http://www.djcxy.com/p/51381.html

上一篇: Randomize a List<T>

下一篇: Automapper behavior differs when mapping lists compared to singe objects