Алгоритм сортировки для рейтинга бинарного выбора

Question

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

Как мне отсортировать мой список книг на основе этого двоичного выбора? У этой проблемы есть официальное название?

Answer 1

Как указывает Йонас Эльфстрём , Фишер-Йейтс - это канонический способ перетасовать набор, и это, вероятно, хорошая идея, поскольку он позволит вам получать данные для каждого элемента.Я думаю, что вы, вероятно, хотите больше, чем один проход, хотя.По сути, при сортировке коллекции элементов вы создаете ориентированный граф, в котором узлами являются элементы, а ребра представляют отношение , большее или равное .Когда можно алгоритмически определить это отношение, тогда будет достаточно одного прохода, и вы получите хорошо упорядоченный набор.

Сложность здесь в том, что очень правдоподобно смотреть на книги по две и позволятьЧеловек решит без четко определенного алгоритма, и в итоге возникнет ситуация, когда A> B, B> C и C> A. Это явно не приведет к хорошо упорядоченному набору.Хуже того, в два разных дня можно было бы дать два разных ответа для одних и тех же двух книг.

Лучший способ сделать это - сохранить матрицу n x n, гдеn - количество сортируемых товаров.запись i, j - это количество раз, когда элемент i был выбран лучше, чем элемент j.Здесь i индексирует строки и j индексирует столбцы.

Отсюда, PageRank , который, к сожалению, запатентован ¹ , будет идеальным.Не так элегантно, но, возможно, достаточно хорошо, чтобы сложить разницу между aij и aji, а затем отсортировать книги на основе этого.Например, сортировка трех книг

   A B C
   _ _ _
 A|0 3 2
 B|2 0 3
 C|1 2 0

будет означать, что A был оценен лучше, чем B 3 раза, и лучше, чем C 2 раза.Суммирование строк дает

 A: (AB - BA) + (AC - CA) = (3 - 2) + (2 - 1) = 2
 B: (BA - AB) + (BC - CB) = (2 - 3) + (3 - 2) = 0
 C: (CA - AC) + (CB - BC) = (1 - 2) + (2 - 3) = -2

Таким образом, они будут сортироваться как A > B > C.

---

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

^{1 Извините за разглагольствование, но я знаю, как вы запатентоваличто по сути математический результат.}

Answer 2

Извините за то, что задели старый вопрос, но я думаю, что это будет полезно для вас.

Когда я работал над той же задачей, я выбираю онлайн-сортировку. Это идеальный выбор для небольшой коллекции. Например, для 10 книг вы должны сделать только 14 сравнений (в среднем случае). В лучшем случае вы должны сделать только 9 сравнений (если ваша коллекция уже отсортирована).

Если вы выбираете быструю сортировку, вам нужно сделать 20 сравнений (в среднем), но это всегда лучше, чем грязная сортировка (сравнивая каждую книгу со всеми книгами в коллекции).

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

Обратите внимание, что все эти решения имеют одно предположение о транзитивных отношениях (если book1 лучше, чем book2 и book2 лучше, чем book3, то book1 лучше, чем book3). Если это не работает для вас - вы не можете их ранжировать.

Вы можете найти оба прекрасно описанных алгоритма в Википедии:
http://en.wikipedia.org/wiki/Insertion_sort
http://en.wikipedia.org/wiki/Quick_sort

Answer 3

Вы можете Фишер-Йейтс перемешать книг и затем получить их два на два.Сравнение только двух экземпляров - это либо отрезок, который можно назвать сортировкой, либо его можно назвать самой основой.