Алгоритм ранжирования на основе сравнения (вариация)

Question

Этот вопрос является вариацией предыдущего вопроса: Алгоритм ранжирования на основе сравнения

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

Здесь я вставил оригинальный вопрос:

"Я хотел бы ранжировать или отсортировать коллекцию элементов (размер которых потенциально может превышать 100 000)где каждый элемент в коллекции не имеет внутреннего (сопоставимого) значения, вместо этого все, что у меня есть, - это сравнение любых двух элементов, которые были предоставлены пользователями «субъективным» образом.

Пример:

Рассмотрим коллекцию с элементами [a, b, c, d] и сравнениями пользователей:

b> a, a> d, d> c

Правильный порядокиз этой коллекции будет [b, a, d, c].

Этот пример прост, однако могут быть более сложные случаи:

Поскольку сравнения субъективны, использованиеМожно также сказать, что с> б.В этом случае это может привести к конфликту с порядком выше.Также вы можете не иметь сравнений, которые «связывают» все элементы, например:

b> a, d> c.В этом случае порядок неоднозначен.Это может быть: [b, a, d, c] или [d, c, b, a].В этом случае любой порядок является приемлемым.

...

Вопрос:

Существует ли уже существующий алгоритм, который может решить вышеуказанную проблему, я бы не сталнравится тратить усилия, пытаясь придумать, если это так.Если конкретного алгоритма не существует, возможно, есть какие-то алгоритмы или методы, на которые вы можете указать мне? "

Answer 1

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

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

• моделирует проблему как направленный граф (то есть тот факт, что a > b подразумевает наличие ребра в результирующем графе, начинающемся в узле "a" и заканчивающемся в узле "b" ).

• вычисляет сильно связанные компоненты (SCC) графика. Короче говоря, SCC - это набор узлов со свойством, которое вы можете получить для любого узла в наборе из любого узла в наборе, следуя списку ребер (это соответствует вашим «циклам» в исходной задаче).

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

• получается, что новый граф, полученный вышеупомянутым способом, является непосредственно ациклическим графом , поэтому мы можем выполнить топологическую сортировку для него.

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