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

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

2 голосов
/ 23 июня 2009

Вот вам загадка.

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

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

Ответы [ 4 ]

7 голосов
/ 23 июня 2009

Сначала перемешайте случайным образом, затем используйте stable sort.

4 голосов
/ 23 июня 2009

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

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

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

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

2 голосов
/ 23 июня 2009

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

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

0 голосов
/ 23 июня 2009

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

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

...