提问



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

最佳参考


使用基于Fisher-Yates shuffle的扩展方法对任何(I)List进行随机播放:[45]


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)提供了一个简单的比较。[46]


编辑:自从几年前写下这个答案以来,很多人都评论或写信给我,指出我比较中的一个很大的愚蠢缺陷。他们当然是对的。 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;
      }
    }
  }
}

其它参考1


如果我们只需要以完全随机的顺序混洗项目(只是为了混合列表中的项目),我更喜欢这个简单而有效的代码,通过guid命令项目......


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

其它参考2


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



  1. 它接受n作为单个输入参数。

  2. 它返回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; 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;
}

其它参考3


IEnumerable的扩展方法:


public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source)
{
    Random rnd = new Random();
    return source.OrderBy<T, int>((item) => rnd.Next());
}

其它参考4


    public static List<T> Randomize<T>(List<T> list)
    {
        List<T> randomizedList = new List<T>();
        Random rnd = new Random();
        while (list.Count > 0)
        {
            int index = rnd.Next(0, list.Count); //pick a random item from the master list
            randomizedList.Add(list[index]); //place it at the end of the randomized list
            list.RemoveAt(index);
        }
        return randomizedList;
    }

其它参考5


修改
RemoveAt是我之前版本的一个弱点。该解决方案克服了这一点。


public static IEnumerable<T> Shuffle<T>(
        this IEnumerable<T> source,
        Random generator = null)
{
    if (generator == null)
    {
        generator = new Random();
    }

    var elements = source.ToArray();
    for (var i = elements.Length - 1; i >= 0; i--)
    {
        var swapIndex = generator.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}


注意可选Random generator,如果Random的基本框架实现不是线程安全的或加密强度足以满足您的需要,您可以将实现注入操作。


在这个答案中可以找到适合线程安全的密码强Random实现的实现。





这是一个想法,以(希望)有效的方式扩展IList。


public static IEnumerable<T> Shuffle<T>(this IList<T> list)
{
    var choices = Enumerable.Range(0, list.Count).ToList();
    var rng = new Random();
    for(int n = choices.Count; n > 1; n--)
    {
        int k = rng.Next(n);
        yield return list[choices[k]];
        choices.RemoveAt(k);
    }

    yield return list[choices[0]];
}




其它参考6


您可以使用这种简单的扩展方法来实现


public static class IEnumerableExtensions
{

    public static IEnumerable<t> Randomize<t>(this IEnumerable<t> target)
    {
        Random r = new Random();

        return target.OrderBy(x=>(r.Next()));
    }        
}


你可以通过以下方式使用它


// use this on any collection that implements IEnumerable!
// List, Array, HashSet, Collection, etc

List<string> myList = new List<string> { "hello", "random", "world", "foo", "bar", "bat", "baz" };

foreach (string s in myList.Randomize())
{
    Console.WriteLine(s);
}

其它参考7


我通常使用:


var list = new List<T> ();
fillList (list);
var randomizedList = new List<T> ();
var rnd = new Random ();
while (list.Count != 0)
{
    var index = rnd.Next (0, list.Count);
    randomizedList.Add (list [index]);
    list.RemoveAt (index);
}

其它参考8


如果你有一个固定的数字(75),你可以创建一个包含75个元素的数组,然后枚举你的列表,将元素移动到数组中的随机位置。您可以使用Fisher-Yates shuffle生成列表编号到数组索引的映射。[48]

其它参考9


当我希望不修改原文时,这是我首选的shuffle方法。它是Fisher-Yatesinside-out算法的变体,适用于任何可枚举的序列(source的长度确实如此)不需要从一开始就知道。[49]


public static IList<T> NextList<T>(this Random r, IEnumerable<T> source)
{
  var list = new List<T>();
  foreach (var item in source)
  {
    var i = r.Next(list.Count + 1);
    if (i == list.Count)
    {
      list.Add(item);
    }
    else
    {
      var temp = list[i];
      list[i] = item;
      list.Add(temp);
    }
  }
  return list;
}


该算法也可以通过分配0length - 1的范围来实现,并通过将随机选择的索引与最后一个索引交换来随机耗尽索引,直到所有索引都被恰好选择一次。上面的代码完成了完全相同的事情,但没有额外的分配。这很漂亮。


关于Random类,它是一个通用数字生成器(如果我正在运行彩票,我会考虑使用不同的东西)。默认情况下,它还依赖于基于时间的种子值。问题的一个小的缓解是用RNGCryptoServiceProvider播种Random类,或者你可以在类似于此的方法中使用RNGCryptoServiceProvider(见下文)来生成统一选择的随机双浮点点值但运行抽奖几乎需要了解随机性和随机源的性质。


var bytes = new byte[8];
_secureRng.GetBytes(bytes);
var v = BitConverter.ToUInt64(bytes, 0);
return (double)v / ((double)ulong.MaxValue + 1);


生成随机双精度(仅在0和1之间)的点是用于缩放到整数解。如果你需要从一个基于随机双x的列表中选择一些东西,那么总是会0 <= x && x < 1是直截了当的。


return list[(int)(x * list.Count)];


请享用!

其它参考10


如果你不介意使用两个Lists,那么这可能是最简单的方法,但可能不是最有效或不可预测的方法:


List<int> xList = new List<int>() { 1, 2, 3, 4, 5 };
List<int> deck = new List<int>();

foreach (int xInt in xList)
    deck.Insert(random.Next(0, deck.Count + 1), xInt);

其它参考11


这是一个有效的Shuffler,它返回一个字节数组的混洗值。它永远不会超过需要的时间。它可以从它之前停止的地方重新启动。我的实际实现(未显示)是一个允许用户指定的MEF组件更换洗牌器。


    public byte[] Shuffle(byte[] array, int start, int count)
    {
        int n = array.Length - start;
        byte[] shuffled = new byte[count];
        for(int i = 0; i < count; i++, start++)
        {
            int k = UniformRandomGenerator.Next(n--) + start;
            shuffled[i] = array[k];
            array[k] = array[start];
            array[start] = shuffled[i];
        }
        return shuffled;
    }


`

其它参考12


 public Deck(IEnumerable<Card> initialCards) 
    {
    cards = new List<Card>(initialCards);
    public void Shuffle() 
     }
    {
        List<Card> NewCards = new List<Card>();
        while (cards.Count > 0) 
        {
            int CardToMove = random.Next(cards.Count);
            NewCards.Add(cards[CardToMove]);
            cards.RemoveAt(CardToMove);
        }
        cards = NewCards;
    }

public IEnumerable<string> GetCardNames() 

{
    string[] CardNames = new string[cards.Count];
    for (int i = 0; i < cards.Count; i++)
    CardNames[i] = cards[i].Name;
    return CardNames;
}

Deck deck1;
Deck deck2;
Random random = new Random();

public Form1() 
{

InitializeComponent();
ResetDeck(1);
ResetDeck(2);
RedrawDeck(1);
 RedrawDeck(2);

}



 private void ResetDeck(int deckNumber) 
    {
    if (deckNumber == 1) 
{
      int numberOfCards = random.Next(1, 11);
      deck1 = new Deck(new Card[] { });
      for (int i = 0; i < numberOfCards; i++)
           deck1.Add(new Card((Suits)random.Next(4),(Values)random.Next(1, 14)));
       deck1.Sort();
}


   else
    deck2 = new Deck();
 }

private void reset1_Click(object sender, EventArgs e) {
ResetDeck(1);
RedrawDeck(1);

}

private void shuffle1_Click(object sender, EventArgs e) 
{
    deck1.Shuffle();
    RedrawDeck(1);

}

private void moveToDeck1_Click(object sender, EventArgs e) 
{

    if (listBox2.SelectedIndex >= 0)
    if (deck2.Count > 0) {
    deck1.Add(deck2.Deal(listBox2.SelectedIndex));

}

    RedrawDeck(1);
    RedrawDeck(2);

}

其它参考13


这是一种线程安全的方法:




public static class EnumerableExtension
{
    private static Random globalRng = new Random();

    [ThreadStatic]
    private static Random _rng;

    private static Random rng 
    {
        get
        {
            if (_rng == null)
            {
                int seed;
                lock (globalRng)
                {
                    seed = globalRng.Next();
                }
                _rng = new Random(seed);
             }
             return _rng;
         }
    }

    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> items)
    {
        return items.OrderBy (i => rng.Next());
    }
}

其它参考14


对接受的答案进行简单修改,返回一个新的列表而不是就地工作,并接受更一般的IEnumerable<T>和其他Linq方法一样多。


private static Random rng = new Random();

/// <summary>
/// Returns a new list where the elements are randomly shuffled.
/// Based on the Fisher-Yates shuffle, which has O(n) complexity.
/// </summary>
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> list) {
    var source = list.ToList();
    int n = source.Count;
    var shuffled = new List<T>(n);
    shuffled.AddRange(source);
    while (n > 1) {
        n--;
        int k = rng.Next(n + 1);
        T value = shuffled[k];
        shuffled[k] = shuffled[n];
        shuffled[n] = value;
    }
    return shuffled;
}

其它参考15


想法是通过项目和随机顺序获得无关的对象,然后按此顺序重新排序项目并返回值:


var result = items.Select(x => new { value = x, order = rnd.Next() })
            .OrderBy(x => x.order).Select(x => x.value).ToList()

其它参考16


老帖子肯定,但我只是使用GUID。


Items = Items.OrderBy(o => Guid.NewGuid().ToString()).ToList();


GUID始终是唯一的,因为每次结果每次更改时都会重新生成GUID。

其它参考17


解决此类问题的一种非常简单的方法是在列表中使用多个随机元素交换。


在伪代码中,这看起来像这样:


do 
    r1 = randomPositionInList()
    r2 = randomPositionInList()
    swap elements at index r1 and index r2 
for a certain number of times