algorithm - 二元选择评级的排序算法

Question

想象一下我想根据自己喜欢的程度订购的书籍 list 。我没有对单本书进行评分，而是从列表中的两本书(随机选择)中选择最好的，然后对任意多对书籍重复此操作(不对所有组合进行评分)。

如何根据这个二元选择对我的图书 list 进行排序？这个问题有正式名称吗？

Answer 1

作为Jonas Elfström指出，Fisher-Yates 是洗牌的规范方式，这可能是个好主意，因为它可以让您获取每个项目的数据。我认为您可能想要不止一次通过。本质上，您在对项目集合进行排序时正在做的是构建一个有向图，其中节点是项目，边表示关系大于或等于。当可以通过算法定义这种关系时，单次传递就足够了，您最终会得到一个有序的集合。

这里的复杂之处在于，非常可信的是，一次看两本书并让人类在没有明确定义的算法的情况下做出决定，最终会出现 A > B，B > C 和 C > A. 这显然不会产生有序的集合。更糟糕的是，在不同的两天，同一两本书可能会给出两个不同的答案。

我能想到的最好的方法是维护一个 n x n矩阵，其中 n是要排序的项目的数量。 i, j条目是该项目的次数i被选为优于项目 j .在这里，i索引行和 j索引列。

从这里开始，PageRank不幸的是，它已获得专利¹，这将是理想的选择。不那么优雅，但可能足以总结 a 之间的差异。 <子> ij 和 a ji然后根据此对书籍进行排序。例如，对三本书进行排序

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

表示 A被评为优于B比C好3倍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 的整数来消除矩阵并获得相同的结果。当A选择超过 B , 递增与 A 关联的整数并减少与 B 关联的整数.

^{1 对不起，我的咆哮，但我知道你如何为本质上是数学结果的专利申请。}