我有一个
n
元素的列表,编号从 1 到 n
,其中每个元素都对其他每个元素进行投票,因此我得到了一个分数方阵。每票都是任意自然数。元素也给自己投票。所以给定一个矩阵:
1 2 3 4
----------------
1 | 3 3 9 11
2 | 7 1 12 5
3 | 11 9 8 7
4 | 5 12 8 3
每一行
i
代表元素i
给其他人的分数,每一列j
代表元素j
从其他人那里得到的“分数”。
我正在寻找一种方法来根据这些分数对数字
1
到n
进行排序。这不是寻找“赢家”或“输家”,而是寻找具有尽可能多的等价类的元素的预序。尝试在理论上尽可能多地实现总订单。
在上面的示例中,可以先按弱降序对每一列进行排序,然后根据列的字典顺序进行预排列,以获得元素的预序:
3 2 1,4
--------------
12 12 11
9 9 7
8 3 5
8 1 3
在这种情况下,3 将是最高元素,其次是 2,并且 1 和 4 是等价元素。但是 1 和 4 可以进一步消除歧义,考虑到元素 4 从元素 1 得到它的分数 11,它在相同的等价类中,但是
1
从元素 3
得到它的分数 11,它在一个更高的等价类, 所以 1
然后高于 4 所以元素排序为:
3 > 2 > 1 > 4
我无法弄清楚我还能找到哪些其他可能性,如何处理潜在的循环等。是否有任何算法试图如上所述组织和排序等价类中的一组元素?
注意: 任何拆分和排序等价类的方法都是受欢迎的,包括考虑以下事项:更慷慨的元素(给其他人更好的分数)比自私的元素(往往不会给出好分数)更好。
注意: 在我的特殊情况下,每个元素总是比其他任何元素都更好地投票给自己。换句话说,每一行
i
在 i
列都有其最大的元素,但我认为这个限制并不重要,这就是为什么我提供的示例不遵循该限制。