隨機洗牌相同元素的排序比較方法

我想改變下面的比較方法，以便當兩個項目被認爲是相等的時候，它們將被隨機洗牌。

myList.Sort((x, y) => x.Score.CompareTo(y.Score));

我可以想像，如果你不想在另一個優先考慮一個結果時，他們的成績是相同的這種情況將在訂貨搜索結果時是有用的。

任何人都想給它一個去嗎？

這是我第一次嘗試解決方案，但它不起作用。我會讓你找出原因。

class RandomizeWhenEqualComparer<T> : IComparer<T> 
{ 
    private readonly Func<T, T, int> _comparer; 

    public int Compare(T x, T y) 
    { 
      if (x.Equals(y)) return 0; 

     int result = _comparer(x, y); 

     if (result != 0) return result; 

     double random = StaticRandom.NextDouble(); 
     return (random < .5) ? -1 : 1; 
    } 

    public RandomizeWhenEqualComparer(Func<T, T, int> comparer) 
    { 
     _comparer = comparer; 
    } 
}

來源

2009-06-23 cbp

閱讀此：http://blogs.msdn.com/oldnewthing/archive/2009/05/08/9595334.aspx（和從那裏鏈接的帖子），找出你爲什麼建議做一個壞的理念。 – AakashM 2009-06-23 07:33:21

如果比較器正確實現並且在爲同一對元素再次調用時返回相同結果，則這不會成爲問題。 – sharptooth 2009-06-23 08:05:57

您可以像銳利齒輪所說的那樣存儲每次比較的結果並再次查找它們。

但這並不好玩，它會增加時間複雜度和空間複雜度，因爲您必須存儲以前的比較結果並在每次進行比較時搜索它們。

這就是我要做的：在搜索開始時，獲得一個隨機種子。然後編寫一個基於T和種子創建哈希的函數。

public int Hash(T a, int s) 
{ 
    // e.g. 
    return Random(a.Name().ToInt() + s).NextDouble(); 
} 

public int Compare(T x, T y, int s) 
{ 
    if (x.Equals(y)) return 0; 

    int result = _comparer(x, y); 

    if (result != 0) return result; 

    return (Hash(x, s) < Hash(y, s)) ? -1 : 1; 
}

這將在給定的排序內穩定，但不需要查找表。

來源

2009-06-23 07:59:19 Geerad

問題是，比較的結果是不能沿着這種排序再現的。排序算法可以針對給定的一對元素多次調用比較方法，並且每次比較方法應該返回相同的值。

您可以存儲涉及隨機洗牌的每個比較結果，並在再次爲相應對調用比較方法時查看它們。

來源

2009-06-23 06:35:45 sharptooth

是的，這是問題，現在解決方案是什麼？ – cbp 2009-06-23 06:36:45

先隨機洗牌，然後用穩定排序。

來源

2009-06-23 06:45:49

這是一個優雅的解決方案。這確實意味着比較策略沒有完全包含在比較類中，這對我來說並不理想，但無論如何它是好的。 – cbp 2009-06-23 06:52:22

如果您只控制排序方法，那麼您將受到嚴格限制，因爲您不知道將使用哪種排序算法。您必須保留相同關鍵值之間的任意比較的隨機結果，並查看任何新的在表中相同值之間的比較以確保相同，穩定的結果在任何單一的排序運行中，就像Sharptooth所說的那樣。

不是嚴格的比較方法，但是如何快速排序算法，您可以隨機將哪個細分的任何值與關鍵值等於透視值一起去？遞歸細分將隨機在左側和右側放置一些相等的值。

來源

2009-06-23 07:27:42

隨機洗牌相同元素的排序比較方法

回答

相關問題