两个结果的最优“交集”算法?

3
我有两个结果,想要得到它们的最佳“顺序”。 例如: 我们进行了两场比赛,第一场比赛有5个人,第二场比赛有7个人。结果如下: 比赛1:
1. Karl
2. Fred
3. John
4. Peter
5. Sid

比赛2。
1. Steven
2. John
3. Karl
4. Peter
5. Aron
6. Fred
7. Kevin

问题是:这两个比赛的前七名是什么?
很明显,在这种情况下,第一名是卡尔,因为他拥有一个第一名和一个第三名,这比约翰的第二名和第三名更好。然而,史蒂文可能同样出色,但他只参加了一场比赛,应该受到某种惩罚。
这个问题有哪些已知的算法?有什么简单的解决方案吗?我就是想不出来。

有趣的问题,不过这取决于你是否有实际比赛时间的数据,而不仅仅依赖于位置。 - David Tang
你的问题到底是什么?“这两个比赛的前七名是谁?”和“这个问题已知的算法有哪些?是否存在一些简单的解决方案?”对我来说似乎是两个完全不同的问题。 - Haozhun
谷歌排名算法。总的来说,它们很难,但是只有两个竞赛,你可能会找到合适的东西。 - moinudin
5
你需要的是一个“规范”,而不是一个“算法”。那么这里有很多不同的答案:以F1积分制为例。 - Antoine Pelisse
3个回答

2
您可以将职位与权重相关联(将其视为得分)。例如,第一个位置的权重为20,第二个位置的权重为18,第三个位置的权重为16,以此类推。参与错过可能与权重-5有关。您可以根据需要调整数字。
要找到最终结果,您需要将每个人的权重相加并比较数字。
我认为这应该有效...

1

另一种方法是创建一个与先前比赛排序一致的顶级节点排序。这可以通过使用max-flow algorithm来完成。


0
一个天真的解决方案是为所有玩家都有一种ID。遍历两个列表,并将任何新的ID添加到另一个列表中,例如称为Positions。将这些ID的所有值设置为某个不能成为比赛位置的大数,称之为BIG_VAL(例如100)。遍历第一个列表,并将所有位置标记为Positions列表中的新值。这只是第一场比赛,所以这里没有什么特别的。然后遍历第二个列表,并将这些ID的第二个位置结果添加到Positions列表中。对于不出现的ID,将其结果再加上一个BIG_VAL。现在,列表将按顺序显示比赛位置,唯一剩下的就是对它们进行排序。在此列表中,Karl将是4,John将是5,Fred将是8,等等。

http://bit.ly/fvYtal


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接