排名 - 最小化成对比较
Ranking - minimizing pair-wise comparison
我有一个包含 100 个项目的列表，我想生成一个排名列表，要求用户对项目对进行评分，提示："Do you prefer item A or item B instead?"。因为询问这些项目的所有可能组合真的很累。例如。如果项目 1 优于项目 2，项目 2 优于项目 3，则无需比较项目 1 和项目 3。
我正在寻找一种算法来减少此类比较并给出完整的排名列表。
如果使用 3 对项目来提高比较次数，那将是首选方式。在这种情况下，用户会对 3 对中最好的和最差的进行评分，因此每 'turn'.
对 3 个项目进行排名
有 100! 个可能的订单。 2^524 < 100! < 2^525 所以你能做的最好的就是 525 二元问题。
3 题版本做得更好。它可以给出 6 种可能的答案，因此通过相同的分析，您最多只能回答 204 个问题。
您不太可能轻易达到这些界限。但是你可以靠近。
对于二进制比较，很难比 Ford-Johnson Merge-Insertion Sort 做得更好。
通过 3 向比较，真正的最佳答案将是一个有趣的研究项目。但是你可以通过找到 3 个元素来 close 来关闭 ，这样最可能的顺序就尽可能地不可能。
精确计算太难了。但是贪婪的方法如下。对于每个元素，计算已知有多少其他元素更好，有多少已知更差。按 "fewest known comparisons" 然后 "smallest difference between better/worse" 然后 "fewest known to be worse" 然后 "original order".
将它们排序到优先级列表中
取此优先级列表中的第一个元素。向下查找列表中从未与之比较过的第一个元素。继续向下寻找第一个从未被比较过的。如果找不到，请寻找从未与第一个进行比较但可能与第二个进行比较的那个。如果做不到这一点，只需比较这对。
举个例子可能会有帮助。让我们尝试使用 3 种比较方式对 2, 4, 1, 3, 5 进行排序。在没有任何信息的情况下，我们起初只是接受我们得到的命令。我们先比较2, 4, 1，发现那是1, 2, 4。此时我们知道：
1: better: 2, 4; worse:
2: better: 4; worse: 1
3: better: ; worse:
4: better: ; worse: 1, 2
5: better: ; worse:
现在我们按最少的比较排序，然后是最好和最差的数量之间的最小差异，然后是最少的最差，然后是原始顺序。这给出 3, 5, 2, 1, 4。已经比较了 3, 5, 2 的 None，所以我们接下来要得到 2, 3, 5。我们现在知道：
1: better: 2, 3, 4, 5; worse:
2: better: 3, 4, 5; worse: 1
3: better: 5; worse: 1, 2
4: better: ; worse: 1, 2
5: better: ; worse: 1, 2, 3
现在我们的优先排序给了我们 4, 3, 5, 2, 1。我们取 4, 5。一切都与其中之一进行了比较，所以我们转到 3 因为它还没有与 4 进行比较。这三者比较3, 4, 5。我们现在知道：
1: better: 2, 3, 4, 5; worse:
2: better: 3, 4, 5; worse: 1
3: better: 4, 5; worse: 1, 2
4: better: 5; worse: 1, 2, 3
5: better: ; worse: 1, 2, 3, 4
我们用 3 三向比较对 5 件事进行了排序。这在理论上是我们能做的最好的。 （当你增加数量时，我怀疑你会经常这样做。但它应该击败二元策略。）
您可以提出 100 个问题，然后要求最好的，然后是次佳的，依此类推 99 个问题，最终得出您的排名。
我有一个包含 100 个项目的列表，我想生成一个排名列表，要求用户对项目对进行评分，提示："Do you prefer item A or item B instead?"。因为询问这些项目的所有可能组合真的很累。例如。如果项目 1 优于项目 2，项目 2 优于项目 3，则无需比较项目 1 和项目 3。
我正在寻找一种算法来减少此类比较并给出完整的排名列表。
如果使用 3 对项目来提高比较次数，那将是首选方式。在这种情况下，用户会对 3 对中最好的和最差的进行评分，因此每 'turn'.
对 3 个项目进行排名有 100! 个可能的订单。 2^524 < 100! < 2^525 所以你能做的最好的就是 525 二元问题。
3 题版本做得更好。它可以给出 6 种可能的答案，因此通过相同的分析，您最多只能回答 204 个问题。
您不太可能轻易达到这些界限。但是你可以靠近。
对于二进制比较，很难比 Ford-Johnson Merge-Insertion Sort 做得更好。
通过 3 向比较，真正的最佳答案将是一个有趣的研究项目。但是你可以通过找到 3 个元素来 close 来关闭 ，这样最可能的顺序就尽可能地不可能。
精确计算太难了。但是贪婪的方法如下。对于每个元素，计算已知有多少其他元素更好，有多少已知更差。按 "fewest known comparisons" 然后 "smallest difference between better/worse" 然后 "fewest known to be worse" 然后 "original order".
将它们排序到优先级列表中取此优先级列表中的第一个元素。向下查找列表中从未与之比较过的第一个元素。继续向下寻找第一个从未被比较过的。如果找不到，请寻找从未与第一个进行比较但可能与第二个进行比较的那个。如果做不到这一点，只需比较这对。
举个例子可能会有帮助。让我们尝试使用 3 种比较方式对 2, 4, 1, 3, 5 进行排序。在没有任何信息的情况下，我们起初只是接受我们得到的命令。我们先比较2, 4, 1，发现那是1, 2, 4。此时我们知道：
1: better: 2, 4; worse:
2: better: 4; worse: 1
3: better: ; worse:
4: better: ; worse: 1, 2
5: better: ; worse:
现在我们按最少的比较排序，然后是最好和最差的数量之间的最小差异，然后是最少的最差，然后是原始顺序。这给出 3, 5, 2, 1, 4。已经比较了 3, 5, 2 的 None，所以我们接下来要得到 2, 3, 5。我们现在知道：
1: better: 2, 3, 4, 5; worse:
2: better: 3, 4, 5; worse: 1
3: better: 5; worse: 1, 2
4: better: ; worse: 1, 2
5: better: ; worse: 1, 2, 3
现在我们的优先排序给了我们 4, 3, 5, 2, 1。我们取 4, 5。一切都与其中之一进行了比较，所以我们转到 3 因为它还没有与 4 进行比较。这三者比较3, 4, 5。我们现在知道：
1: better: 2, 3, 4, 5; worse:
2: better: 3, 4, 5; worse: 1
3: better: 4, 5; worse: 1, 2
4: better: 5; worse: 1, 2, 3
5: better: ; worse: 1, 2, 3, 4
我们用 3 三向比较对 5 件事进行了排序。这在理论上是我们能做的最好的。 （当你增加数量时，我怀疑你会经常这样做。但它应该击败二元策略。）
您可以提出 100 个问题，然后要求最好的，然后是次佳的，依此类推 99 个问题，最终得出您的排名。