Я хотел бы ранжировать или сортировать коллекцию элементов (с размером потенциально более 100 000), когда элементы в коллекции не имеют собственного (сопоставимого) значения, вместо этого все, что у меня есть, это сравнение между любыми двумя элементами, которые были предоставлены пользователями субъективным образом.
Пример. Рассмотрим коллекцию с элементами [a, b, c, d]
и сравнениями пользователями b > a
, a > d
, d > c
. Правильный порядок этой коллекции будет [b, a, d, c]
.
Этот пример прост, однако могут быть более сложные случаи:
- Поскольку сравнения являются субъективными, пользователь также может сказать, что
c > b
. В этом случае это приведет к конфликту с указанным выше порядком. - Также у вас могут не быть сравнения, которые "соединяют" все элементы, т.е.
b > a
,d > c
. В этом случае упорядочение неоднозначно. Это может быть[b, a, d, c]
или[d, c, b, a]
. В этом случае допустимо либо упорядочение.
Если возможно, было бы неплохо как-то учесть несколько экземпляров одного и того же сравнения и дать тем, у кого больше вложений, больше веса. Но решение без этого условия было бы приемлемым.
Аналогичное применение этого алгоритма использовалось приложением Zuckerberg FaceMash, где он оценивал людей на основе сравнений (если я правильно понял), но я не смог найти, что это за алгоритм.
Есть ли уже существующий алгоритм, который может решить проблему выше? Я бы не хотел тратить силы, пытаясь придумать один, если это так. Если нет конкретного алгоритма, существуют ли определенные типы алгоритмов или методов, на которые вы можете указать мне?