随机化列表<T>

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

606868 次浏览
小开

如果您有一个固定的数字（75），您可以创建一个包含75个元素的数组，然后枚举您的列表，将元素移动到数组中的随机位置。您可以使用费希尔-耶茨洗牌生成列表号到数组索引的映射。

小开

我通常使用：

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

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

在伪代码中，它看起来像这样：

dor1 = randomPositionInList()r2 = randomPositionInList()swap elements at index r1 and index r2for a certain number of times
小开 
    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 listrandomizedList.Add(list[index]); //place it at the end of the randomized listlist.RemoveAt(index);}return randomizedList;}
小开
最佳答案

使用基于费希尔-耶茨洗牌的扩展方法对任何(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. Cryptograph中的随机数生成器，如下所示：

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

IENumable的扩展方法：

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

如果我们只需要以完全随机的顺序洗牌项目（只是为了混合列表中的项目），我更喜欢这个简单而有效的代码，它可以通过guid…

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

正如人们在评论中指出的那样，GUID不能保证是随机的，所以我们应该使用真正的随机数生成器：

private static Random rng = new Random();...var shuffledcards = cards.OrderBy(a => rng.Next()).ToList();
小开

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

小开

这是一个高效的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;}

'

小开

这里有一个线程安全的方法来做到这一点：

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());}}
小开

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

我对这个简单算法的所有笨拙版本感到有点惊讶。Ferer-Yates（或Knuth Shuffle）有点棘手，但非常紧凑。为什么它很棘手？因为你需要注意你的随机数生成器r(a,b)返回的值是b的包含值还是排他值。我还编辑了维基百科描述，这样人们就不会盲目地在那里遵循伪代码，并创建难以检测的错误。对于. Net，Random.Next(a,b)返回不包括b的数字，所以不用多说，这是它在C#/. Net中的实现方式：

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

试试这个代码

小开 
 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();}

elsedeck2 = 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);
}
小开

您可以实现这是使用这个简单的扩展方法

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

老职位肯定，但我只是使用GUID。 

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

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

小开

当不需要修改原始时，这是我首选的洗牌方法。它是费舍尔-耶茨“由内而外”算法的变体，适用于任何可枚举序列（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)];

好好享受！

小开

接受的答案的简单修改，它返回一个新列表而不是就地工作，并像许多其他Linq方法一样接受更通用的IEnumerable<T>。

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

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

var result = items.Select(x => new { value = x, order = rnd.Next() }).OrderBy(x => x.order).Select(x => x.value).ToList()
小开 
    List<T> OriginalList = new List<T>();List<T> TempList = new List<T>();Random random = new Random();int length = OriginalList.Count;int TempIndex = 0;
while (length > 0) {TempIndex = random.Next(0, length);  // get random value between 0 and original lengthTempList.Add(OriginalList[TempIndex]); // add to temp listOriginalList.RemoveAt(TempIndex); // remove from original listlength = OriginalList.Count;  // get new list <T> length.}
OriginalList = new List<T>();OriginalList = TempList; // copy all items from temp list to original list.
小开

我在网上找到了一个有趣的解决方案。

礼貌：https://improveandrepeat.com/2018/08/a-simple-way-to-shuffle-your-lists-in-c/

var Shuffled=myList. OrderBy（x=>Guide. NewGuid（））. ToList（）；

小开

这是一个允许指定要返回的元素数量的Ferer-Yates洗牌的实现；因此，在获取所需数量的元素之前，没有必要先对整个集合进行排序。

交换元素的顺序从默认值颠倒；并从第一个元素前进到最后一个元素，因此检索集合的子集会产生与洗牌整个集合相同的（部分）序列：

collection.TakeRandom(5).SequenceEqual(collection.Shuffle().Take(5)); // true

该算法基于Durstenfeld在维基百科上的费希尔-耶茨洗牌（现代）版本。

public static IList<T> TakeRandom<T>(this IEnumerable<T> collection, int count, Random random) => shuffle(collection, count, random);public static IList<T> Shuffle<T>(this IEnumerable<T> collection, Random random) => shuffle(collection, null, random);private static IList<T> shuffle<T>(IEnumerable<T> collection, int? take, Random random){var a = collection.ToArray();var n = a.Length;if (take <= 0 || take > n) throw new ArgumentException("Invalid number of elements to return.");var end = take ?? n;for (int i = 0; i < end; i++){var j = random.Next(i, n);(a[i], a[j]) = (a[j], a[i]);}
if (take.HasValue) return new ArraySegment<T>(a, 0, take.Value);return a;}
小开

你的问题是如何随机化列表。这意味着：

  1. 所有独特的组合都应该有可能发生
  2. 所有唯一的组合应该出现在相同的分布（AKA是无偏的）。

针对这个问题发布的大量答案不符合上述“随机”的两个要求。

这是一个紧致的、无偏的伪随机函数，遵循费舍尔-耶茨洗牌方法。

public static void Shuffle<T>(this IList<T> list, Random rnd){for (var i = list.Count-1; i > 0; i--){var randomIndex = rnd.Next(i + 1); //maxValue (i + 1) is EXCLUSIVElist.Swap(i, randomIndex);}}
public static void Swap<T>(this IList<T> list, int indexA, int indexB){var temp = list[indexA];list[indexA] = list[indexB];list[indexB] = temp;}
小开

只是想建议使用IComparer<T>和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());
小开

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

安装程序包morelinq

using MoreLinq;...var randomized = list.Shuffle();
小开 
private List<GameObject> ShuffleList(List<GameObject> ActualList) {

List<GameObject> newList = ActualList;List<GameObject> outList = new List<GameObject>();
int count = newList.Count;
while (newList.Count > 0) {
int rando = Random.Range(0, newList.Count);
outList.Add(newList[rando]);
newList.RemoveAt(rando);
     

}
return (outList);
}

用法：

List<GameObject> GetShuffle = ShuffleList(ActualList);
小开

您可以通过使用元组进行交换来使费舍尔-耶茨洗牌更加简洁和富有表现力。

private static readonly Random random = new Random();
public static void Shuffle<T>(this IList<T> list){int n = list.Count;while (n > 1){n--;int k = random.Next(n + 1);(list[k], list[n]) = (list[n], list[k]);}}
小开

我们可以为List使用扩展方法并使用线程安全的随机生成器组合。

public static class ListExtensions{public static void Shuffle<T>(this IList<T> list){if (list == null) throw new ArgumentNullException(nameof(list));int n = list.Count;while (n > 1){n--;int k = ThreadSafeRandom.Next(n + 1);(list[n], list[k]) = (list[k], list[n]);}}}
internal class ThreadSafeRandom{private static readonly Random _global = new Random();private static readonly ThreadLocal<Random> _local = new ThreadLocal<Random>(() =>{int seed;lock (_global){seed = _global.Next();}return new Random(seed);});
public static int Next(int maxValue){return _local.Value.Next(maxValue);}}

我已经将它打包在NuGet上，源代码在github上可用。

小开

执行：

public static class ListExtensions{public static void Shuffle<T>(this IList<T> list, Random random){for (var i = list.Count - 1; i > 0; i--){int indexToSwap = random.Next(i + 1);(list[indexToSwap], list[i]) = (list[i], list[indexToSwap]);}}}

示例：

var random = new Random();var array = new [] { 1, 2, 3 };array.Shuffle(random);foreach (var item in array) {Console.WriteLine(item);}

. NET Fiddle中的演示


提交答案