随机化List <T>

Question

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

Answer 1

随机播放任何(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;
      }
    }
  }
}

Answer 2

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

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

Answer 3

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

1. 它接受n作为单个输入参数.
2. 它从0返回数ñ 包容性.

但.Net随机数生成器不满足#2属性.的b,而不是返回数目从0到n-1以下.如果您尝试反向使用for循环,则需要调用Random.Next(a,b)哪个添加一个额外的操作.

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

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

Answer 4

IEnumerable的扩展方法:

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

Answer 5

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

Answer 6

编辑 这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]];
}

Answer 7

想法是获得具有项目和随机顺序的匿名对象，然后按照此顺序对项目重新排序并返回值：

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

Answer 8

可以使用 morelinq 包中的 Shuffle 扩展方法，它适用于 IEnumerables

安装包 morelinq

using MoreLinq;
...    
var randomized = list.Shuffle();

Answer 9

只是想建议使用IComparer<T>and的变体List.Sort()：

public class RandomIntComparer : IComparer<int>
{
    private readonly Random _random = new Random();
    
    public int Compare(int x, int y)
    {
        return _random.Next(-1, 2);
    }
}

用法：

list.Sort(new RandomIntComparer());

Answer 10

从 .NET 8 开始，您可以使用Shuffle()：

//Argument is Span<T> or T[]
Random.Shared.Shuffle(mySpan);

或者，对于密码学上的强随机性：

//Argument is Span<T>
RandomNumberGenerator.Shuffle(mySpan);

对于列表，您必须先创建一个数组 ( myList.ToArray()) 如上所示进行混洗，然后从混洗后的数组创建一个新列表

Answer 11

如果您不介意使用两个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);

Answer 12

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

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

Answer 13

当希望不修改原始文件时，这是我首选的 shuffle 方法。它是Fisher–Yates“由内而外”算法的变体，适用于任何可枚举序列（source不需要从一开始就知道的长度）。

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

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

关于Random该类，它是一个通用数字生成器（如果我正在运行彩票，我会考虑使用不同的东西）。默认情况下，它还依赖于基于时间的种子值。该问题的一个小缓解是Random使用RNGCryptoServiceProvider或您可以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)];

享受！