是使用随机和OrderBy一个很好的洗牌算法？
我在Coding Horror上看过一篇关于各种洗牌算法的文章。 我已经看到有人在这个地方打乱了一个清单：
var r = new Random();
var shuffled = ordered.OrderBy(x => r.Next());
这是一个很好的洗牌算法吗？ 它是如何工作的？ 这是一个可接受的方式吗？
这并不是我喜欢的一种洗牌方式，主要是因为它很容易实现O（n）洗牌时没有理由，因此它是O（n log n）。 问题中的代码“工作”，基本上给每个元素一个随机的（希望是唯一的！）数字，然后根据该数字对元素进行排序。
我更喜欢Durstenfield的Fisher-Yates shuffle变体，它交换元素。
实现一个简单的Shuffle扩展方法基本上包括在输入上调用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;
}
}
编辑：下面的表现的评论提醒我，我们可以在我们洗牌时实际返回元素：
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实例：
Random实例将产生相同的随机数序列（当以相同的方式使用时） Random不是线程安全的。 我有一篇关于Random的文章，详细介绍这些问题并提供解决方案。
这是基于Jon Skeet的回答。
在那个答案中，数组被洗牌，然后使用yield返回。 最终的结果是，数组在foreach期间保存在内存中，以及迭代所需的对象，但成本始终在开始 - yield基本上是一个空循环。
这个算法在游戏中被广泛使用，其中前三个选项被挑选出来，而其他的只在后面才需要。 我的建议是yield尽快为他们进行交换的数字。 这将减少启动成本，同时保持O（1）的迭代成本（基本上每次迭代5次操作）。 总成本将保持不变，但洗牌本身会更快。 在这种情况下，这被称为collection.Shuffle().ToArray()它理论上没有区别，但在上述使用情况下，它将加速启动。 此外，这将使该算法适用于只需要几个独特项目的情况。 例如，如果你需要从52 deck.Shuffle().Take(3)牌中抽出3张牌，你可以调用deck.Shuffle().Take(3) ，只有三次交换（尽管整个数组必须先被复制）。
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];
}
从这个Skeet的报价开始：
这并不是我喜欢的一种洗牌方式，主要是因为它很容易实现O（n）洗牌时没有理由，因此它是O（n log n）。 问题中的代码“工作”，基本上给每个元素一个随机的（ 希望是唯一的！ ）数字，然后根据该数字对元素进行排序。
我会稍微解释一下希望独特的原因！
现在，从Enumerable.OrderBy：
此方法执行稳定的排序; 也就是说，如果两个元素的键相等，则元素的顺序被保留
这个非常重要！ 如果两个元素“接收”相同的随机数会发生什么？ 恰好它们保持与它们在数组中的顺序相同。 现在，发生这种情况的可能性有多大？ 很难准确计算，但生日问题就是这个问题。
现在，它是真的吗？ 这是真的吗？
一如既往，如有疑问，请写下一些程序：http：//pastebin.com/5CDnUxPG
这个小块代码使用向后完成的Fisher-Yates算法将3个元素的数组重新排序，向前完成Fisher-Yates算法（在wiki页面中有两个伪代码算法......它们产生等效结果，但是一个是从第一个到最后一个元素完成的，而另一个是从最后一个元素到第一个元素完成的），http://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))
为了测试这个问题是否存在，我们可以放大数组（非常慢）或者简单地减少随机数生成器的最大值（ int.MaxValue不是一个“特殊”数字......它只是一个非常大的数字）。 最后，如果算法不受OrderBy稳定性的影响，那么任何值的范围都应该给出相同的结果。
程序然后测试一些值，范围在1 ... 4096。 看看结果，很明显，对于低值（<128），该算法非常有偏见（4-8％）。 有了3个值，你至少需要r.Next(1024) 。 如果你增大阵列（4或5），那么甚至r.Next(1024)是不够的。 我不是洗牌和数学方面的专家，但我认为，对于数组的每个额外位数，您需要额外2位的最大值（因为生日悖论连接到sqrt（numvalues）），所以如果最大值是2 ^ 31，我会说你应该能够排列高达2 ^ 12/2 ^ 13位的数组（4096-8192个元素）
上一篇: Is using Random and OrderBy a good shuffle algorithm?
下一篇: How do I override GetHashCode() without any numbers as fields?