在对项之间反复选择后确定排序的算法

Question

我想写一个小程序来帮助我根据许多一对一比较的结果对项目进行排序。

因此，如果我有100个条目，我将允许用户重复地在这组中的两个随机选择项中进行选择。假设总共有10.000张选票。第10号项目在1000票中胜出，并赢得了与所有其他项目的直接对抗。第90条以100票获胜，赢得40票，输掉了60次直接对抗。是否有一种现有的算法(例如，来自推荐系统或类似的算法)，可以用来构造这些项目的排序列表？

Answer 1

一个简单的方法是根据win percentage (即total wins/total confrontations )进行排序。

如果你想有一个单一的得分机制，你可以reward的赢家和punish的输家的固定数量，然后排名根据最后的分数。

最后，您可以看看Elo ranking algorithm，它计算了每个项目赢得对抗的概率，以及rewards and punishes相对于这些概率的概率。

示例

# Probability
A higher chance of winning than B

# Case1: A wins
A +small reward
B -small punishment

# Case2: B wins
A -large punishment
B +large reward

Answer 2

如果您只想做您解释的(您没有要求任何优化或类似的)，那么算法是非常简单的。

1. 建立所有可能比较的矩阵。
2. 按其列中获胜的数量对每个元素进行排序。

在伪代码中，这可能如下所示：

# given a list of elements:
elements = ...

# build the comparison matrix:
matrix = Matrix(n, n)
for i in 0..n-1:
  for j in 0..n-1:
    matrix[i][j] = elements[i] < elements[n]

# rank each element by its "wins":
for i in 0..n-1:
  ranks[i] = sum(matrix[i])

在此之后，ranks[i]将说明每个i的elements[i]级别，这样您就可以按照ranks对elements进行排序。