Я хотел бы ранжировать или отсортировать коллекцию предметов (с размером, потенциально превышающим 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]. В этом случае любой заказ приемлем.
Если возможно, было бы неплохо как-то принять во внимание несколько экземпляров одного и того же сравнения и придать весам более высокие случаи. Но решение без этого условия все равно будет приемлемым.
Аналогичное приложение этого алгоритма использовалось приложением Цукерберга FaceMash, в котором он оценивал людей на основе сравнений (если я правильно понял), но я не смог найти, что это был за алгоритм на самом деле.
Существует ли уже существующий алгоритм, который может решить описанную выше проблему? Я не хотел бы тратить усилия, пытаясь придумать один, если это так. Если нет конкретного алгоритма, возможно, есть ли определенные типы алгоритмов или методов, на которые вы можете указать мне?