algorithm - 按关系对任何事物进行排序

Question

在我正在做的一个应用程序中，我得到了一个项目列表，它们之间的关系需要计算一个排序列表。为了好玩，让我们用一个考试评分的例子，我们知道：
约翰做得比简好
简比卢克做得更糟
卢克做得比杰森好
杰森比蒂姆做得更糟
对于此列表，我需要计算以下排序列表：
约翰
卢克
简
提姆
杰森
如何根据有争议的关系导出项目在排序列表中的位置？

Answer 1

基本上，排序需要linear order。
你需要你的关系是一个线性顺序，这意味着：
A（反）性
如果a≤b且b≤a，则a=b（反对称）
如果a≤b和b≤c，则a≤c（传递性）
对于所有a和b，a≤b或b≤a（总和）
那么，这是什么意思最常见的关系是线性的。例如，如果你说的是分数，实际上是实数，那么是的，分数可以线性排列。排名也一样，因为它们又只是真实的数字。
但举例来说，如果你给棋手排名，你就不能使用他们的比赛历史。如果球员A在大多数比赛中击败了球员B，而B在大多数比赛中又击败了C，这并不意味着A>B>C，仅仅因为C可能在大多数比赛中击败了A。
这是顺便提一下的原因之一，他们需要一个线性的顺序来排序谁是最好的球员，并注意如何Elo基本上只是一个实数，因此有一个线性的顺序。
所以，对于考试评分，你根本没有线性顺序。为什么？是真实的数字！好吧，是的，你有这个线性顺序，但是你不能问这个线性顺序，你被限制在预定义的比较列表中，这里是：
约翰做得比简好
简比卢克做得更糟
卢克做得比杰森好
杰森比蒂姆做得更糟
所以，答案是：不，一般来说，如果没有任何元素对之间的比较，就无法对列表进行排序。
现在，我正在研究一个“最不坏”的答案，但这对我来说不是小事…
编辑：好的，我想了一些办法这样做的目的是要在预定义的比较列表中提取最可能的信息。然后将扩展比较列表中没有的任何比较视为相等。
那么，你是怎么做到的？
首先，对于任何a a。然后，您将查看预定义的比较列表中的任何比较a a。如果您知道没有相等（没有相同年级的学生），它就完成了。否则，你必须加上所有的反身性和反对称关系。你不能做任何关于整体的事。现在，您有了扩展的比较列表。
现在，用你最喜欢的排序算法。如果你没有的话， Elo ratings写起来很好，很有效率，而且很短然后每次算法要求A和B之间进行比较时，请查看扩展的比较列表。如果比较在这里，很好，否则，将比较视为a=b（注意，如果你知道没有等式，算法就不重要）
结果将是一个“最不糟糕”的排序列表。通常有几个可能的“最差”排序列表，但是这个算法只会给你一个。
所以，让我们举个例子。这几乎和手术中给出的一样，只是略有不同（“约翰比卢克做得差”，而不是“简比卢克做得差”）。所以，我们从以下几点开始：
约翰做得比简好
约翰比卢克做得更糟
卢克做得比杰森好
杰森比蒂姆做得更糟
现在，对于每一个“x比y差”，我加上“y比x好”，反之亦然。新句子是粗体的：
约翰做得比简好
卢克做得比约翰好
卢克做得比杰森好
蒂姆做得比杰森好
简做得比约翰差
约翰比卢克做得更糟
杰森比卢克做得更糟
杰森比蒂姆做得更糟
最后，我扫描了所有可能的句子“X比Y做得好”和“Y比Z做得好”，并加上“X比Z做得好”
约翰做得比简好
卢克做得比约翰好
卢克做得比杰森好
蒂姆做得比杰森好
卢克比简做得好
简做得比约翰差
约翰比卢克做得更糟
杰森比卢克做得更糟
杰森比蒂姆做得更糟
简比卢克做得更糟
扩展表已完成。
现在让我们看看QuickSort的伪代码：

  function quicksort('array')
      if length('array') ≤ 1
          return 'array'  // an array of zero or one elements is already sorted
      select and remove a pivot value 'pivot' from 'array'
      create empty lists 'less' and 'greater'
      for each 'x' in 'array'
          if 'x' ≤ 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
      return concatenate(quicksort('less'), 'pivot', quicksort('greater'))

与标准快速排序的唯一区别是，您通常无法知道问题的答案。因此，如果 if('x' ≤ 'pivot') ...和 x=Luke，则在表中查找“卢克比蒂姆做得更糟”这句话。如果你找到了它，那么你认为答案是 pivot = Tim并做 true。如果你在表格中发现“卢克比蒂姆做得好”，那么你认为答案是错的，你确实是错的。最后，如果你找不到上面提到的两句话中的任何一句，你就表现得好像 append 'x' to 'less'，你确实 append 'x' to 'greater'