使用IComparer的洗牌

Question

首先，我知道费舍-耶茨洗牌的事。但是为了参数起见，我想让用户从下拉列表中选择一个排序选项。这份清单将包括一个“随机”选项。根据它们的选择结果，我只想在IComparer实例中替换我的排序。IComparer会是什么样子？

谷歌提出了大量有缺陷的结果，这些结果都是这样的：

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实例，因为我看不到任何其他方法:必须使用其他的、真正随机的值来比较项，但对于给定排序操作中的项，该值也必须是一致的。

我有一个start 这里，但是它发布得很匆忙，速度非常慢，甚至没有返回所有可能的类型(测试表明，如果不计算丢失的选项，它至少可以消除偏见)。我不期望O (n )的性能像Fisher-Yates那样，但我确实想要一些合理的东西(n log表示一个小的ish n)，而且我确实希望它能显示出所有可能的类型。不幸的是，这个链接是目前被接受的答案，所以我希望能够用一些更好的方法来代替它。

如果没有别的，我希望这是一个磁铁，所有的谷歌查询寻找一个IComparable解决方案-他们将结束在这里，而不是其他地方告诉他们使用错误的版本。

Answer 1

我在其他地方得到的一个建议是创建一个单独的IArranger接口，该接口描述一个用于安排集合的操作。这可以在IComparer/I比较仪无法工作的情况下工作，因为它对整个集合进行操作，而不是对单个项操作。它看起来可能是这样的：

public interface IArranger<T>
{
    IEnumerable<T> Arrange(IEnumerable<T> items);
}

然后，我可以使用适当的Fisher-Yates算法实现来自IArranger接口的IArranger，还可以实现包装我所关心的每个附加IEnumerable.Sort()/IComparable/IComparer品种的实现。看起来可能是这样的：

public class ComparerArranger<T> : IArranger<T>
{
    private IComparer<T> comparer;

    public ComparableArranger(IComparer<T> comparer)
    {
        this.comparer = comparer;
    }

    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
       return items.OrderBy(i => i, comparer);
    }
}

或

//uses the default Comparer for the type (Comparer<T>.Default)
public class TypeArranger<T> : IArranger<T> 
{
    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
       return items.OrderBy(i => i);
    }
}

或

public class ShuffleArranger<T> : IArranger<T>
{
    //naive implementation for demonstration
    // if I ever develop this more completely I would try to
    // avoid needing to call .ToArray() in here
    // and use a better prng
    private Random r = new Random();

    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
        var values = items.ToArray();

        //valid Fisher-Yates shuffle on the values array
        for (int i = values.Length; i > 1; i--)
        {
            int j = r.Next(i);
            T tmp = values[j];
            values[j] = values[i - 1];
            values[i - 1] = tmp;
        }
        foreach (var item in values) yield return item;
    }
}

作为最后一步，我通过扩展方法将对此的支持添加到任何IEnumerable中。然后，您仍然可以得到简单的运行时算法交换，您可以更好地实现洗牌算法，并且使用的代码感觉很自然：

public static IEnumerable<T> Arrange(this IEnumerable<T> items, IArranger<T> arranger)
{
    return arranger.Arrange(items);
}

Answer 2

我在这条线上发布了多少错误答案，这让我有点惊讶。只是为了其他想出类似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次左右执行排序过程，您将得到一个错误声明：

IComparer (or the IComparable methods it relies upon) did not return zero when Array.Sort called x. CompareTo(x). x: '0' x's type: 'Int32' The 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 (oops!)。无论您使用Guid、GetHashCode或任何其他随机生成的输入，像上面所示的解决方案仍然是错误的。

尽管如此，Fisher-Yates是调整数组的标准方法，因此没有真正的理由使用IComparer。Fisher-Yates是O(n)，而任何使用IComparer的实现都在场景后面使用快速排序，其时间复杂度为O(n log )。没有充分的理由不使用著名的、高效的、标准的算法来解决这类问题。

但是，如果您确实坚持使用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;

Answer 3

IComparer在某个点要求零返回(对于相同的T实例)，使得在数学上不可能创建一个通用的IComparer，从而在统计上模仿费舍-耶茨洗牌。总会有偏见的。对于真正的洗牌，您永远不想强迫它返回任何特定的值。