是使用随机和OrderBy一个很好的洗牌algorithm？
我在Coding Horror上看了一篇关于各种shufflealgorithm的文章 。 我看到有人在这个地方打乱了一个清单：
var r = new Random(); var shuffled = ordered.OrderBy(x => r.Next()); 这是一个很好的洗牌algorithm吗？ 它是如何工作的？ 这是一个可以接受的方式吗？
这不是我喜欢的洗牌方式，主要是因为它很容易实现O（n）洗牌，所以没有理由就是O（n log n）。 基本上给每个元素一个随机的（希望是唯一的！）数字，然后根据这个数字对元素进行sorting，问题中的代码“起作用”。
我更喜欢Durstenfield的Fisher-Yates shuffle变体，它交换元素。
实现一个简单的Shuffle扩展方法基本上包括在input上调用ToList或ToArray ，然后使用现有的Fisher-Yates实现。 （传入Random作为参数，使生活通常更好。）周围有很多实现…我可能有一个在某个地方的答案。
关于这种扩展方法的好处是，读者将清楚你实际上正在做什么。
编辑：这是一个简单的实现（没有错误检查！）：
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng) { T[] elements = source.ToArray(); // Note i > 0 to avoid final pointless iteration for (int i = elements.Length-1; i > 0; i--) { // Swap element "i" with a random earlier element it (or itself) int swapIndex = rng.Next(i + 1); T tmp = elements[i]; elements[i] = elements[swapIndex]; elements[swapIndex] = tmp; } // Lazily yield (avoiding aliasing issues etc) foreach (T element in elements) { yield return element; } }
编辑：下面的performance的评论提醒我，我们可以实际上返回的元素，我们洗牌：
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng) { T[] elements = source.ToArray(); for (int i = elements.Length - 1; i >= 0; i--) { // Swap element "i" with a random earlier element it (or itself) // ... except we don't really need to swap it fully, as we can // return it immediately, and afterwards it's irrelevant. int swapIndex = rng.Next(i + 1); yield return elements[swapIndex]; elements[swapIndex] = elements[i]; } }
现在只会做尽可能多的工作。
请注意，在这两种情况下，您需要注意Random使用的实例：
- 在大致相同的时间创build两个
Random实例将产生相同的随机数序列（当以相同的方式使用时） -
Random不是线程安全的。
我有一篇关于Random的文章，详细介绍这些问题并提供解决scheme。
这是基于Jon Skeet的回答 。
在这个答案中，数组被洗牌，然后使用yield返回。 最终的结果是数组在foreach期间保存在内存中，以及迭代所需的对象，但是开始的代价是全部 – 成本基本上是一个空循环。
这个algorithm在游戏中被使用了很多，前三个选项被选中，而其他的则只有后来才需要。 我的build议是尽快交换数字。 这将减less启动成本，同时保持O（1）的迭代成本（基本上每次迭代5次操作）。 总成本将保持不变，但洗牌本身会更快。 在这种情况下，这被称为collection.Shuffle().ToArray()它理论上将没有任何区别，但在上述使用情况下，它将加快启动。 此外，这将使algorithm有用的情况下，你只需要一些独特的项目。 例如，如果你需要从52 deck.Shuffle().Take(3)牌中抽出3张牌，你可以调用deck.Shuffle().Take(3)只有三次交换（尽pipe整个数组必须先被复制）。
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng) { T[] elements = source.ToArray(); // Note i > 0 to avoid final pointless iteration for (int i = elements.Length - 1; i > 0; i--) { // Swap element "i" with a random earlier element it (or itself) int swapIndex = rng.Next(i + 1); yield return elements[swapIndex]; elements[swapIndex] = elements[i]; // we don't actually perform the swap, we can forget about the // swapped element because we already returned it. } // there is one item remaining that was not returned - we return it now yield return elements[0]; }
对于大多数目的而言，它几乎总是可以的，并且几乎总是会产生一个真正的随机分布（除非Random.Next（）产生两个相同的随机整数）。
它通过为系列的每个元素分配一个随机整数，然后按这些整数对序列进行sorting来工作。
99.9％的应用程序完全可以接受（除非你绝对需要处理上面的边缘情况）。 此外，双向运行的反对意见是有效的，所以如果你正在洗一个长列表，你可能不想使用它。
从这个Skeet的报价开始：
这不是我喜欢的洗牌方式，主要是因为它很容易实现O（n）洗牌，所以没有理由就是O（n log n）。 基本上给每个元素一个随机的（ 希望是唯一的！ ）数字，然后根据这个数字对元素进行sorting，问题中的代码“起作用”。
我会稍微解释一下希望独特的原因！
现在，从Enumerable.OrderBy ：
这种方法执行稳定的sorting; 也就是说，如果两个元素的键相等，则元素的顺序被保留
这个非常重要！ 如果两个元素“接收”相同的随机数，会发生什么？ 碰巧它们仍然与数组中的顺序保持一致。 现在有什么可能发生？ 确切地计算是困难的，但生日问题正是这个问题。
现在，这是真的吗？ 这是真的吗？
一如既往，如有疑问，请写下一些程序： http : //pastebin.com/5CDnUxPG
这个小块代码使用向后完成的Fisher-Yatesalgorithm将3个元素的数组重新sorting，向前完成Fisher-Yatesalgorithm（在wiki页面中有两个伪代码algorithm…它们产生等效结果，但是一个是从第一个到最后一个元素，而另一个是从最后到第一个元素完成的），天真的错误algorithmhttp://blog.codinghorror.com/the-danger-of-naivete/和使用.OrderBy(x => r.Next())和.OrderBy(x => r.Next(someValue)) 。
现在， Random.Next是
大于或等于0且小于MaxValue的32位有符号整数。
所以它相当于
OrderBy(x => r.Next(int.MaxValue))
为了testing这个问题是否存在，我们可以放大数组（非常慢的数组）或简单地减less随机数生成器的最大值（ int.MaxValue不是一个“特殊”数字…它只是一个非常大的数字）。 最后，如果algorithm不受OrderBy稳定性的影响，则任何值的范围都应该给出相同的结果。
程序然后testing一些值，范围在1 … 4096。 看看结果，很明显，对于低值（<128），algorithm是非常有偏见的（4-8％）。 有了3个值，你至less需要r.Next(1024) 。 如果你把数组r.Next(1024) 4或5），那么甚至r.Next(1024)是不够的。 我不是洗牌和math方面的专家，但是我认为对于数组的每个额外的位，你需要额外的2位的最大值（因为生日悖论连接到sqrt（numvalues）），所以如果最大值是2 ^ 31，我会说你应该能够排列高达2 ^ 12/2 ^ 13位（4096-8192个元素）
看起来像一个很好的洗牌algorithm，如果你不是太担心的performance。 我指出的唯一问题是它的行为是不可控的，所以你可能很难testing它。
一个可能的select是将一个种子作为parameter passing给随机数发生器（或随机发生器作为参数），这样就可以更容易地进行控制和testing。
稍微不相关的，但这是一个有趣的方法（即使它真的是过度，真的已经实施）真正的随机生成骰子卷！
骰子-O-Matic的
我在这里发表的原因是他提出了一些有趣的观点，关于他的用户如何反应使用algorithm来洗牌的想法，而不是真正的骰子。 当然，在现实世界中，这样的解决scheme只是针对频谱的真正极端，随机性有如此大的影响，也许影响到了金钱）。
这已经出现了很多次。 在StackOverflow上searchFisher-Yates。
这里是我为这个algorithm编写的C＃代码示例 。 如果您愿意，您可以在其他types的参数化。
static public class FisherYates { // Based on Java code from wikipedia: // http://en.wikipedia.org/wiki/Fisher-Yates_shuffle static public void Shuffle(int[] deck) { Random r = new Random(); for (int n = deck.Length - 1; n > 0; --n) { int k = r.Next(n+1); int temp = deck[n]; deck[n] = deck[k]; deck[k] = temp; } } }
我会说在这里有很多答案，比如“这个algorithm通过为列表中的每个值生成一个新的随机值，然后按这些随机值对列表进行sorting”可能是非常错误的！
我认为这不会为源集合的每个元素分配一个随机值。 相反，可能会有一个像Quicksort一样运行的sortingalgorithm，它可能会调用一个比较函数大约n个n次。 algortihm真的希望这个比较函数是稳定的，总是返回相同的结果！
难道IEnumerableSorter不是为每个快速sorting的algorithm步骤调用一个比较函数， x => r.Next()每次都调用函数x => r.Next()来x => r.Next()这两个参数！
在这种情况下，你可能真的搞乱了sortingalgorithm，使得它比预期的algorithm更糟糕。 当然，它最终会变得稳定，并返回一些东西。
我稍后可以通过在新的“Next”函数中joindebugging输出来检查它，看看会发生什么。 在Reflector中，我无法立即知道它是如何工作的。
我发现Jon Skeet的答案是完全令人满意的，但是我的客户的机器人扫描器会报告Random任何实例作为安全缺陷。 所以我换了System.Security.Cryptography.RNGCryptoServiceProvider 。 作为奖励，它修复了所提到的线程安全问题。 另一方面， RNGCryptoServiceProvider测量速度比使用Random慢300 RNGCryptoServiceProvider 。
用法：
using (var rng = new RNGCryptoServiceProvider()) { var data = new byte[4]; yourCollection = yourCollection.Shuffle(rng, data); }
方法：
/// <summary> /// Shuffles the elements of a sequence randomly. /// </summary> /// <param name="source">A sequence of values to shuffle.</param> /// <param name="rng">An instance of a random number generator.</param> /// <param name="data">A placeholder to generate random bytes into.</param> /// <returns>A sequence whose elements are shuffled randomly.</returns> public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, RNGCryptoServiceProvider rng, byte[] data) { var elements = source.ToArray(); for (int i = elements.Length - 1; i >= 0; i--) { rng.GetBytes(data); var swapIndex = BitConverter.ToUInt32(data, 0) % (i + 1); yield return elements[swapIndex]; elements[swapIndex] = elements[i]; } }
寻找一个algorithm？ 你可以使用我的ShuffleList类：
class ShuffleList<T> : List<T> { public void Shuffle() { Random random = new Random(); for (int count = Count; count > 0; count--) { int i = random.Next(count); Add(this[i]); RemoveAt(i); } } }
然后，像这样使用它：
ShuffleList<int> list = new ShuffleList<int>(); // Add elements to your list. list.Shuffle();
它是如何工作的？
我们来看一下5个第一个整数的初始sorting列表： { 0, 1, 2, 3, 4 } 。
该方法首先计算元素的数量并将其称为count 。 然后，在每一步count递减的情况下，它将取一个介于0和count之间的随机数，并将其移动到列表的末尾。
在下面的分步示例中，可以移动的项目是斜体 ，所选项目是粗体 ：
0 1 2 3 4
0 1 2 3 4
0 1 2 4 3
0 1 2 4 3
1 2 4 3 0
1 2 4 3 0
1 2 3 0 4
1 2 3 0 4
2 3 0 4 1
2 3 0 4 1
3 0 4 1 2
该algorithm通过为列表中的每个值生成一个新的随机值，然后通过这些随机值对列表进行sorting。 把它看作是在内存表中添加一个新列，然后用GUID填充，然后按该列进行sorting。 看起来像对我来说是一个有效的方式（特别是与lambda糖！）
启动时运行代码清除所有线程和caching每个新的testing，
首先不成功的代码。 它在LINQPad上运行。 如果你按照testing这个代码。
Stopwatch st = new Stopwatch(); st.Start(); var r = new Random(); List<string[]> list = new List<string[]>(); list.Add(new String[] {"1","X"}); list.Add(new String[] {"2","A"}); list.Add(new String[] {"3","B"}); list.Add(new String[] {"4","C"}); list.Add(new String[] {"5","D"}); list.Add(new String[] {"6","E"}); //list.OrderBy (l => r.Next()).Dump(); list.OrderBy (l => Guid.NewGuid()).Dump(); st.Stop(); Console.WriteLine(st.Elapsed.TotalMilliseconds);
list.OrderBy（x => r.Next（））使用38.6528毫秒
list.OrderBy（x => Guid.NewGuid（））使用36.7634毫秒（从MSDN推荐）。
在第二次之后他们两个在同一时间使用。
编辑：testing代码在英特尔酷睿i7 4@2.1GHz，Ram 8 GB DDR3 @ 1600，硬盘SATA 5200转每分钟[数据：www.dropbox.com/s/pbtmh5s9lw285kp/data]
使用系统;
使用System.Runtime;
使用System.Diagnostics;
使用System.IO;
使用System.Collections.Generic;
使用System.Collections;
使用System.Linq;
使用System.Threading;
命名空间algorithm
{
上课程序
{
public static void Main（string [] args）
{
尝试{
int i = 0;
int limit = 10;
var result = GetTestRandomSort（limit）;
foreach（结果中的var元素）{
Console.WriteLine（）;
Console.WriteLine（“time {0}：{1} ms”，++ i，element）;
}
catch（Exception e）{
Console.WriteLine（e.Message）;
最后{
Console.Write（“按任意键继续...”）;
Console.ReadKey（真）;
}
}
公共静态IEnumerable <double> GetTestRandomSort（int限制）
{
for（int i = 0; i <5; i ++）{
string path = null，temp = null;
秒表st = null;
StreamReader sr = null;
诠释？ count = null;
List <string> list = null;
随机r = null;
所以GC.Collect（）;
GC.WaitForPendingFinalizers（）;
Thread.sleep代码（5000）;
st = Stopwatch.StartNew（）;
#region导入input数据
path = Environment.CurrentDirectory +“\\ data”;
list = new List <string>（）;
sr = new StreamReader（path）;
count = 0;
while（count <limit &&（temp = sr.ReadLine（））！= null）{
// Console.WriteLine（temp）;
list.Add（温度）;
计数++;
}
sr.Close（）;
#endregion
// Console.WriteLine（“-------------- Random --------------”）;
// #region用OrderBysorting（random.Next（））
// r = new Random（）;
// list = list.OrderBy（l => r.Next（））。ToList（）;
// #endregion
// #region按OrderBysorting（Guid）
// list = list.OrderBy（l => Guid.NewGuid（））。ToList（）;
// #endregion
// #region按Random和OrderBysorting（random.Next（））
// r = new Random（）;
// list = list.AsParallel（）。OrderBy（l => r.Next（））。ToList（）;
// #endregion
//＃地区sorting随机并行OrderBy（Guid）
// list = list.AsParallel（）。OrderBy（l => Guid.NewGuid（））。ToList（）;
// #endregion
//＃地区按用户定义的随机播放方式随机sorting
// r = new Random（）;
// list = list.Shuffle（r）.ToList（）;
// #endregion
//＃地区sorting随机与并行用户定义随机播放方法
// r = new Random（）;
// list = list.AsParallel（）。Shuffle（r）.ToList（）;
// #endregion
//结果
//
st.Stop（）;
产量回报st.Elapsed.TotalMilliseconds;
foreach（var元素在列表中）{
Console.WriteLine（元件）;
}
}
}
}
}
结果说明： https : //www.dropbox.com/s/9dw9wl259dfs04g/ResultDescription.PNG
结果统计： https ： //www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNG
结论：
假设：在第一个解决scheme中，LINQ OrderBy（r.Next（））和OrderBy（Guid.NewGuid（））不会比用户定义的混洗方法差。
答：他们是矛盾的。
