随机化一个List <T>

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

使用基于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方法来select交换候选项。 速度很快,但不像应该那样随机。 如果你需要更好的随机性质量,可以使用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方法中的rngvariables,如果这个方法将被重复调用,那么这个方法会很麻烦。 下面是一个固定的,完整的例子,基于今天从@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(); 

我对这个简单algorithm的所有笨重的版本感到有点惊讶。 Fisher-Yates(或Knuth shuffle)有点棘手,但非常紧凑。 如果你去维基百科,你会看到这个algorithm的版本反向循环,很多人似乎并不明白为什么它是相反的。 关键的原因是这个版本的algorithm假设随机数发生器Random(n)在你的处理有以下两个属性:

  1. 它接受n作为单个input参数。
  2. 它返回从0到n的数字。

但是.Net随机数发生器不满足#2属性。 Random.Next(n)将返回从0到n-1的数字。 如果你尝试使用for-loop,那么你需要调用Random.Next(n+1) ,这会增加一个额外的操作。

然而,.Net随机数发生器有另外一个很好的函数Random.Next(a,b) ,它返回a到b-1(含)。 这实际上非常适合于具有正常循环的algorithm的实现。 所以,不要紧张,这是正确,高效和紧凑的实现:

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

IEnumerable的扩展方法:

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

编辑 RemoveAt是我以前的版本中的一个弱点。 该解决scheme克服了这一点。

 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 generator的基本框架实现不是线程安全的或者足够强大以满足您的需要,则可以将您的实现注入到操作中。

在这个答案中可以find适合线程安全的密码强度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]]; } 

你可以用这个简单的扩展方法来实现

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

我通常使用:

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

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

这是我希望不修改原文的首选洗牌方法。 它是Fisher-Yates“内外”algorithm的一个变体,可以在任何可枚举的序列上工作( 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; } 

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

关于Random类,它是一个通用的数字发生器(如果我正在运行一个彩票,我会考虑使用不同的东西)。 它也默认依靠基于时间的种子值。 解决这个问题的一个小小的解决办法是使用RNGCryptoServiceProviderRandom类进行种子处理,或者使用RNGCryptoServiceProvider类似于这个方法(见下面)来生成统一select的随机双浮点值,但是运行抽奖需要理解随机性和随机性来源的性质。

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

产生一个随机双(仅在0和1之间)的点是用来缩放到一个整数解。 如果你需要从一个列表中select一个基于随机双x ,它总是0 <= x && x < 1是直截了当的。

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

请享用!

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

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

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

老职位肯定,但我只是使用一个GUID。

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

GUID始终是唯一的,并且每次结果每次都会更新,因此它将被重新生成。

接受的答案的一个简单的修改,返回一个新的列表,而不是就地工作,并接受更一般的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; } 

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

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

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