Метод сравнения для сортировки, который случайным образом перемещает одинаковые элементы

Question

Для вас это загадка.

Я хочу изменить следующий метод сравнения, так что, когда два элемента считаются равными, они будут случайным образом перемешаны.

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; 
    } 
} 

Answer 1

Вы можете, как сказал sharptooth, сохранить результат для каждого сравнения и снова просмотреть их.

Но это не весело, и это увеличивает временную сложность и сложность пространства, так как вы должны хранить предыдущие сравнения и искать их каждый раз, когда делаете сравнение.

Итак, вот что я сделал: В начале поиска получите случайное семя. Затем напишите функцию, которая создает хэш на основе как 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; 
} 

Это будет стабильным в заданном виде, но не требует таблицы поиска.

Answer 2

Проблема заключается в том, что результат сравнения не воспроизводится вдоль сортировки. Алгоритм сортировки может многократно вызывать метод сравнения для данной пары элементов, и метод сравнения должен возвращать одинаковое значение каждый раз.

Вы можете сохранить результат каждого сравнения, связанного с случайным перетасовкой, и просмотреть их, когда метод сравнения снова будет вызван для соответствующей пары.

Answer 3

Сначала производите его случайным образом, затем используйте стабилизатор .

Answer 4

Если вы используете только метод сортировки, то вы сильно ограничены, так как не знаете, какой алгоритм сортировки он будет использоваться. Вам нужно будет сохранить рандомизированные результаты любого сравнения между равными ключевыми значениями и посмотреть любые новые сравнение между равными значениями в таблице для обеспечения того же стабильного результата в любом отдельном прогоне сортировки, например, говорит Sharptooth.

Не совсем метод сравнения, но как насчет алгоритма быстрой сортировки, в котором вы производите случайное определение, в какое подразделение происходит любое значение с ключом, равным значению поворота? Рекурсивное подразделение будет случайным образом размещать некоторые равные значения слева, а некоторые - справа.