使用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);