c# - 使用 IComparer 随机播放

Question

首先，我确实知道 Fisher-Yates 洗牌。但是为了争论起见，我想允许用户从下拉列表中选择一个排序选项。该列表将包括一个“随机”选项。根据他们的选择结果，我只想用 IComparer 实例代替我的排序。 IComparer 会是什么样子？

Google 提出了大量有缺陷的结果，这些结果都采用这种形式:

public class NaiveRandomizer<T> : IComparer<T>
{
    private static Random rand = new Random();

    public int Compare(T x, T y)
    {
        return (x.Equals(y))?0:rand.Next(-1, 2);
    }
}

但是，这种实现是有偏见的，在某些情况下甚至会抛出异常。可以使用以下代码演示偏差:

void Test()
{
    Console.WriteLine("NaiveRandomizer Test:");
    var data = new List<int>() {1,2,3};
    var sortCounts = new Dictionary<string, int>(6);
    var randomly = new NaiveRandomizer<int>();

    for (int i=0;i<10000;i++)
    {   //always start with same list, in _the same order_.
        var dataCopy = new List<int>(data); 
        dataCopy.Sort(randomly);

        var key = WriteList(dataCopy);
        if (sortCounts.ContainsKey(key))
            sortCounts[key]++;
        else
            sortCounts.Add(key, 1);
    }

    foreach (KeyValuePair<string, int> item in sortCounts)
        Console.WriteLine(item.Key + "\t" + item.Value);
}

string WriteList<T>(List<T> list)
{
   string delim = "";
   string result = "";
   foreach(T item in list)
   {
       result += delim + item.ToString();
       delim = ", ";
   }
   return result;
}

那么你如何实现一个随机的 IComparer<T>那解决了那些问题？允许要求每次调用 .Sort()使用单独的 IComparer 实例，因为我看不到任何其他方法可以做到这一点:项目必须使用其他一些真正随机的值进行比较，但该值必须对于给定排序操作中的项目也保持一致。

我有一个开始here ，但它是匆忙发布的，非常慢，甚至不返回所有可能的排序(测试表明它至少消除了偏见，如果你不计算缺失的选项)。我不期望像 Fisher-Yates 这样的 O(n) 性能，但我确实想要一些合理的东西(n log n 为一个小的 n)，我确实希望它显示所有可能的种类。不幸的是，该链接是当前接受的问题答案，因此我希望能够用更好的东西替换它。

如果不出意外，我希望它能吸引所有那些寻找 IComparable 解决方案的谷歌查询 - 他们最终会在这里而不是其他地方告诉他们使用不正确的版本。

Answer 1

我在this thread中有些惊讶发布了多少错误答案。只是为了其他提出类似于 OP 发布的解决方案的人，以下代码看起来是正确的:

int[] nums = new int[1000];
for (int i = 0; i < nums.Length; i++)
{
    nums[i] = i;
}

Random r = new Random();
Array.Sort<int>(nums, (x, y) => r.Next(-1, 2));

foreach(var num in nums)
{
    Console.Write("{0} ", num);
}

但是，代码偶尔会抛出异常，但并非总是如此。这就是让调试变得有趣的原因:) 如果你运行它足够多次，或者在一个循环中执行排序过程 50 次左右，你会得到一个错误说明:

当 Array.Sort 调用 x 时，IComparer(或其依赖的 IComparable 方法)未返回零。比较(x)。 x: '0' x 的类型:'Int32' IComparer: ''。

换句话说，快速排序将一些数字 x 与自身进行了比较，得到了一个非零结果。代码的明显解决方案是编写:

Array.Sort<int>(nums, (x, y) =>
    {
        if (x == y) return 0;
        else return r.NextDouble() < 0.5 ? 1 : -1;
    });

但即使这样也行不通，因为在某些情况下，.NET 将 3 个数字相互比较会返回不一致的结果，例如 A > B、B > C 和 C > A(哎呀!)。无论您使用 Guid、GetHashCode 还是任何其他随机生成的输入，如上所示的解决方案仍然是错误的。

---

话虽如此，Fisher-Yates 是洗牌数组的标准方法，因此首先没有真正的理由使用 IComparer。 Fisher-Yates 是 O(n)，而任何使用 IComparer 的实现都在幕后使用快速排序，其时间复杂度为 O(n log n)。没有充分的理由不使用众所周知的、高效的、标准的算法来解决这类问题。

但是，如果您真的坚持使用 IComparer 和 rand，请在排序之前应用您的随机数据。这需要将数据投影到另一个对象上，这样您就不会丢失随机数据:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Pair<T, U>
    {
        public T Item1 { get; private set; }
        public U Item2 { get; private set; }
        public Pair(T item1, U item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Pair<int, double>[] nums = new Pair<int, double>[1000];
            Random r = new Random();
            for (int i = 0; i < nums.Length; i++)
            {
                nums[i] = new Pair<int, double>(i, r.NextDouble());
            }

            Array.Sort<Pair<int, double>>(nums, (x, y) => x.Item2.CompareTo(y.Item2));

            foreach (var item in nums)
            {
                Console.Write("{0} ", item.Item1);
            }

            Console.ReadKey(true);
        }
    }
}

或者让你的坏人得到 LINQy:

Random r = new Random();
var nums = from x in Enumerable.Range(0, 1000)
           orderby r.NextDouble()
           select x;