使用IComparer随机播放

Question

首先，我确实了解了Fisher-Yates shuffle。但让我们说出于理由，我想让用户从下拉列表中选择一个排序选项。该列表将包括一个“随机”选项。根据他们的选择结果，我只想在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实例，因为我没有看到任何其他方式做到这一点：项目必须使用一些其他的，真正的随机值进行比较，但该值必须也对于给定排序操作中的项目是一致的。

我有一个开始here，但它被张贴在仓促，是非常慢，甚至不返回所有可能的排序（测试表明，它确实至少消除偏差，如果不计算缺少选项）。我不希望像Fisher-Yates这样的O（n）表现，但我确实需要一些合理的东西（对于一个小型的n n来说），而且我希望它能展示所有可能的类型。不幸的是，该链接是目前公认的答案，因此我希望能够用一些更好的东西来替代它。

如果没有其他的东西，我希望这是所有那些寻找IComparable解决方案的谷歌查询的磁铁 - 他们最终会在这里而不是别的地方告诉他们使用不正确的版本。

Answer 1

我在别处得到的一个建议是创建一个单独的IArranger接口，它描述了一个单一的操作，以排列一个集合。这可以在IComparer/IComparable无法使用的地方工作，因为它在整个集合上运行，而不是单个项目。它可能是这个样子：

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

然后，我可以使用适当的费雪耶茨算法实现从IArranger接口Shuffle，也有包装每增加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

如何根据隐藏字段进行排序，该隐藏字段是预先分配的随机值？

Answer 3

我有些惊讶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个左右的时候，你会得到一个错误，指出：

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（哎呀！）。无论您使用Guid，GetHashCode还是任何其他随机生成的输入，上面显示的解决方案都是错误的。

---

有了这样说，费雪耶茨洗牌是阵列的标准方法，所以有在第一时间使用的IComparer没有真正的理由。 Fisher-Yates是O（n），而任何使用IComparer的实现都会在具有O（n log n）时间复杂度的场景后面使用快速排序。没有理由不使用众所周知的高效标准算法来解决这类问题。

但是，如果你真的坚持使用IComparer和一个兰德，那么在你排序前应用你的随机数据。这就要求数据到另一个物体的投影，这样你就不会失去你的随机数据：与你的坏自我

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 4

的IComparer 需要在零回报某些点（对于T的相同实例），使得它在数学上不可能创建一个通用IComparer，它将统计模拟Fisher-Yates Shuffle。总会有偏见。对于一个真正的洗牌，你永远不想强迫它返回任何特定的值。

Answer 5

为了跟上James Curran的想法：让IComparer将“已排序”值保存为一个列表;如果出现新值，请将其插入列表的随机位置;按列表索引进行比较。通过将列表维护为平衡树或其他内容来进行优化。这种IComparer的每个实例都将保持一致的随机排序顺序，因此您可以选择让您的随机排序每次始终保持相同的随机排序或不同的顺序。如果您更喜欢以这种方式阅读“随机”的话，小修改甚至可以将相同的元素“排序”到不同的排序位置。

Answer 6

一个有趣的尝试。很可能是滥用/滥用IComparer。

您正试图通过使用不是为此目的而构建的机制进行随机加权排序。

为什么不实施你自己的排序程序和你自己的比较器？我有一种感觉，即使这样也不够。

Answer 7

不要这样做。

迄今为止提出的所有算法都在输出中引入了某种偏差（比其他偏大）。

@Princess和@Luke建议在数据旁边存储一个随机数。然而，因为这些随机数中的任何两个可能具有与另一个相同的值，所以这两个项之间的排序顺序将被确定性地偏向。

最糟糕的情况是如果排序例程“稳定“（也就是说，被认为相等的对象总是按照输入的顺序输出）。 Array.Sort不会发生稳定（它在内部使用QuickSort），但是当两个项目具有相同的值（取决于它们在输入中的位置）时仍然存在偏差（具体而言，它们与QuickSort的相对位置枢）。

随着此随机数的密钥空间增加，碰撞概率降低（带有很好的随机性），但请记住，随着要排序的值数量增加，生日悖论会指示其中至少有一对相互碰撞的可能性很快上升。

对于一个整数键，该键有2^32个唯一值，并且即使假定有一个完全均匀的随机值分布，有75,000行，存在碰撞的概率为50％。 Wikipedia。

您提出的密码散列方法可能具有足够大的密钥空间（160）位以使得碰撞几率可以忽略不计，但是在实际进行比较之前，您的算法会将所有随机性分解回单个int否定了更大密钥空间的好处。

您的最佳方法是将不同的“sortOrder”值与每个数据项相关联，然后使用经验证的算法对这些值进行洗牌，然后按该值对结果进行排序。

如果您使用的是Array.Sort，那么会有一个重载需要一个“keys”数组和一个“values”数组。 keys数组是按正常顺序排序的，但每当keys数组中的值被移动时，values数组中的相应条目也会移动。

喜欢的东西：

Something[] data;//populated somewhere 
int[] keys = new int[data.Length];//or long if you might have lots of data 
for(int i=0;i<keys.Length;++i) { 
keys[i] = i; 
} 

Shuffle(keys); 

Array.Sort(keys, data);