使用Random和OrderBy作为洗牌算法是一个好的选择吗？

Question

我已经阅读了一篇文章，该文章涉及多种洗牌算法，文章来自于Coding Horror。我看到有些人使用以下方式对列表进行洗牌：

var r = new Random();
var shuffled = ordered.OrderBy(x => r.Next());

这是一个好的洗牌算法吗？它究竟是如何工作的？这是一种可接受的方法吗？

- Svish

Answer 1

我不喜欢这种洗牌的方法，主要是因为它是O(n log n)的，没有什么好的理由，而且很容易实现O(n)的洗牌。问题中的代码"工作"的原理基本上是给每个元素赋予一个随机数（希望是唯一的！），然后根据该数字对元素进行排序。

我更喜欢Durstenfeld的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

---

在StackOverflow上找到关于类似这样的小而重要的实现方式总是很不错的，所以如果您愿意的话，请翻译这个内容。 - Svish

Jon - 你对Fisher-Yates算法的解释与问题中给出的实现是等价的（即朴素版本）。Durstenfeld/Knuth通过从递减集合中选择和交换来实现O(n)的时间复杂度，而不是通过赋值来实现。这种方法可以允许重复选择随机数，并且该算法只需要O(n)的时间复杂度。 - tvanfosson

您可能已经厌烦了我就这个问题不断地和您联系，但我在单元测试中遇到了一个小问题，您可能需要知道。ElementAt存在一些特殊情况，每次都会调用扩展方法，导致结果不可靠。为了避免这种情况，在检查之前，我会先将结果实例化。 - tvanfosson

@tvanfosson：我一点也不生病 :) 但是，呼叫者应该意识到它是惰性评估的。 - Jon Skeet

略晚了一些，但请注意 source.ToArray(); 需要你在同一文件中使用 using System.Linq;。如果没有导入这个命名空间，你会得到这个错误：'System.Collections.Generic.IEnumerable<T>' does not contain a definition for 'ToArray' and no extension method 'ToArray' accepting a first argument of type 'System.Collections.Generic.IEnumerable<T>' could be found (are you missing a using directive or an assembly reference?)。 - Powerlord

Answer 2

这基于Jon Skeet的answer。

在那个答案中，数组被洗牌，然后使用yield返回。净结果是数组和迭代所需的对象在foreach期间都保留在内存中，但成本只出现在开始时 - yield基本上是一个空循环。

这个算法在游戏中经常使用，其中选择前三个项目，其他项目仅在以后（如果有必要）才需要。我的建议是一旦交换数字，就立即yield它们。这将减少启动成本，同时将迭代成本保持在O(1)（基本上每次迭代5个操作）。总成本将保持不变，但洗牌本身会更快。在调用collection.Shuffle().ToArray()的情况下，理论上不会有任何区别，但在上述用例中，它将加速启动。此外，这将使算法对于仅需要少量唯一项的情况非常有用。例如，如果您需要从一副52张牌的牌组中抽出三张牌，则可以调用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]; 
}

- configurator

---

@Svish: 一个极端的例子：rng.Next(i + 1) 可能 每次都返回零，就像一个掷硬币能连续十五次正面朝上一样。虽然它不太可能实际连续N次为零，但很有可能出现一定次数的重复，因此完全覆盖的机会相当低。 - P Daddy

等一下。没事。我没有注意到。半交换处理了重复的随机数。如果每次都是零，它只会有效地颠倒除第一个元素以外的所有元素。 - P Daddy

然而，仍存在一个小问题。这将仅返回N-1个元素。如果源中有10个元素，则仅返回其中的9个。在for循环之后添加yield return elements [0];以进行更正。 - P Daddy

或者你可以将 > 0 替换为 >= 0，这样就不必（虽然会多一次 RNG 命中和冗余赋值）。 - FryGuy

启动成本为O(N)，因为源代码的ToArray()操作的成本是O(N)。 - Dave Hillier

Answer 3

以下是Skeet的一句话：

我不喜欢这种洗牌方式，主要是因为它的复杂度为O(n log n)，但没有什么好的理由，因为很容易实现一个O(n)的洗牌算法。该问题中的代码“有效”地为每个元素分配一个（希望是独一无二的！）随机数，然后根据该数对元素进行排序。

接下来，我会稍微解释一下希望是独一无二的！的原因。

现在，看一下Enumerable.OrderBy：

此方法执行稳定排序；也就是说，如果两个元素的键相等，则元素的顺序保持不变。

这非常重要！如果两个元素“接收”相同的随机数会发生什么？它们将按照它们在数组中的顺序保持不变。那么，这种情况发生的可能性是多少呢？确切地计算很困难，但有一个生日悖论正好是这个问题。

那么，这是真的吗？

像往常一样，如果有疑问，请编写一些程序：http://pastebin.com/5CDnUxPG

这个小代码块使用Fisher-Yates算法反向洗牌包含三个元素的数组若干次，使用正向的Fisher-Yates算法（在wiki页面中有两个伪代码算法...它们产生等效的结果，但一个从第一个元素到最后一个元素完成，而另一个从最后一个元素到第一个元素完成），使用错误的天真算法以及使用.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，我会说您应该能够对包含4096-8192个元素的数组进行排序。

- xanatos

---

表述得很好，完美地展示了原问题的问题所在。这应该与Jon的答案合并。 - TheSoftwareJedi

Answer 4

对于大多数情况来说，这样做可能是可以的，并且几乎总是生成真正随机的分布（除非Random.Next()产生两个相同的随机整数）。

它的工作原理是为序列的每个元素分配一个随机整数，然后按这些整数对序列进行排序。

对于99.9%的应用程序来说，这是完全可接受的（除非您绝对需要处理上述边缘情况）。此外，skeet对其运行时间的反对是有效的，因此如果您要洗牌一个长列表，您可能不想使用它。

- ripper234

Answer 5

这个问题之前已经出现过很多次。请在StackOverflow上搜索Fisher-Yates。

这里有一个我为该算法编写的C#代码示例。如果你愿意，可以将其参数化为其他类型。

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

- hughdbrown

---

你不应该像这样将 Random 用作静态变量 - Random 不是线程安全的。请参阅 http://csharpindepth.com/Articles/Chapter12/Random.aspx - Jon Skeet

@Jon Skeet：当然，那是一个合理的论点。另一方面，OP正在询问一个完全错误的算法，而这个算法是正确的（除了多线程洗牌用例）。 - hughdbrown

这只是意味着这种方法比原始帖子的方法“更正确”。这并不意味着它的代码可以在多线程环境中安全使用，而你没有提到这一点。静态成员可以在多个线程中安全使用是一个合理的期望。 - Jon Skeet

@Jon Skeet：当然，我可以更改它。完成了。我倾向于认为，回到三年半前回答的问题，并说：“它不正确，因为它不能处理多线程使用情况”，而OP从未询问过任何超出算法的内容是过度的。回顾我多年来的答案。通常我会给OP回复，超出了规定的要求。我曾因此受到批评。虽然我不希望OP得到适用于所有可能用途的答案。 - hughdbrown

@Jon Skeet：也许你应该警告人们不要将Random的静态实例传递给你的函数：public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)。这可能会引起问题。 - hughdbrown

Answer 6

寻找算法？您可以使用我的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();

它是如何工作的？

我们先拿一个初始已排好序的整数列表来讲解： { 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

- SteeveDroz

---

那不是O(n)。仅RemoveAt本身就是O(n)。 - paparazzo

嗯，看来你是对的，我的错！我会删除那部分。 - SteeveDroz

Answer 7

我发现Jon Skeet的答案完全令人满意，但是我的客户机器人扫描程序会将任何Random实例报告为安全漏洞。因此，我将其替换为System.Security.Cryptography.RNGCryptoServiceProvider。作为奖励，它修复了被提到的线程安全问题。另一方面，RNGCryptoServiceProvider的速度比使用Random慢300倍。

用法：

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

- frattaro

Answer 8

似乎这是一个不错的洗牌算法，如果你不太在意性能。唯一的问题是它的行为是不可控的，所以你可能会很难测试它。

一个可能的选择是传递一个种子作为参数给随机数生成器（或将随机生成器作为参数），这样你就可以更好地控制和测试它。

- Samuel Carrijo

Answer 9

这个算法通过为列表中的每个值生成一个新的随机值，然后根据这些随机值对列表进行排序来实现洗牌。可以将其看作是向内存表添加一个新列，然后用GUID填充该列，最后按照该列排序。我认为这是一种有效的方法（尤其是使用lambda语法糖时！）

- Dave Swersky

Answer 10

稍微有些不相关，但这里有一个有趣的方法（即使它非常过度，但确实已经被实现）用于真正随机生成骰子点数！

Dice-O-Matic

我在这里发布的原因是，他提出了一些有趣的观点，关于他的用户如何对使用算法洗牌而不是实际骰子的想法做出反应。当然，在现实世界中，这样的解决方案只适用于极端情况，其中随机性具有如此重大的影响，也许影响到金钱；）。

- Irfy