一尘不染

如何合并有序首选项的集合

algorithm

我有一组r审稿人,他们对一组n个对象进行评级。每个审阅者独立地产生他或她选择排名的对象的有序列表。目标是产生一个列表,该列表是各种有序列表的排序规则。我们可以假设每个审阅者的观点具有同等的权重。

这与大多数合并列表和有序列表的问题不同,因为没有全局排序。一个审稿人可以对A> B进行评分,而另一个审稿人可以对B>
A进行评分。如上所述,每个对象不一定都由每个审稿人进行评分。

我目前的想法是将每个审阅者的列表分解为列表中m (m-1)
.5唯一对条目中每对的一组有序元组,其中m是所评级的对象数。现在,从所有审阅者那里获取所有元组。对于给定的组合(a,b),找到所有这样的元组,并将(那些投票中的)多数票作为a
<b的决定因素。

现在,我有一组有序的元组,它们代表了所有人的智慧。但是,如何将它们变成一个有序列表?我可以从随机选择的一对对象开始,对它们进行排序,然后以正确的顺序添加另一个对象,但是输出将取决于我选择从哪个对象开始。也可能有循环。

我将不胜感激。


阅读 237

收藏
2020-07-28

共1个答案

一尘不染

一个看起来很优雅并且仍然需要做的解决方案是将每个排序转换为从1到0的分数,其中1是给定审阅者列表中排名第一(排名靠前)的项目,而0是他们的最后一个(底部项目)
),则介于两者之间的所有项目均会获得线性比例的得分。因此,如果审阅者1仅对3个项目进行排名,那么他们将获得该列表的1、0.5和0的分数。然后,您只需将每个项目的平均分数作为一个整理列表即可。领带可能会因某件商品的“评论”数而中断(因此,由3名评论者一致标记为最佳的项目在最终列表中的出现要高于由2名评论者一致标记为最佳的项目,等等。)

您的要求“目标是生成一个列表,该列表是各种有序列表的排序规则。我们可以假设每个审阅者的观点具有同等的权重。”
这个简单的算法肯定可以满足要求,但是一旦您深入研究此类问题,通常它们的要求就会更加复杂。

2020-07-28