算法:根据“分数矩阵”对一组数字进行排序

问题描述 投票:0回答:0

我有一个

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
列都有其最大的元素,但我认为这个限制并不重要,这就是为什么我提供的示例不遵循该限制。

algorithm sorting
© www.soinside.com 2019 - 2024. All rights reserved.