algorithm - 对知道某些元素比较结果的列表进行排序？

Question

目标是使用包含 m 个比较结果( bool 值)的列表 C 对包含 n 个未知变量 {x0, x1, x2, ... x(n-1)} 的列表 X 进行排序。每个比较都在 n 个变量中的两个之间进行，例如x2 < x5，并且每个比较的对索引是固定的并提前给出。还给出:C 中的所有对都是唯一的(即使翻转时，例如对 x0，x1 意味着没有对 x1，x0)，并且永远不要将变量与自身进行比较。这意味着 C 最多有 n*(n-1)/2 个条目。

所以问题是我能否证明我的 m 比较列表 C 足以对列表 X 进行排序？显然，如果 C 是最大可能的长度(有所有可能的比较)。但是更短的列表呢？

然后，如果已证明 C 包含足够的信息来进行排序，那么我该如何实际执行排序。

Answer 1

让我们假设您有一组要排序的对象，并根据每个对象形成一个节点的图形。然后，您将获得一个配对列表，指示比较的进行情况。您可以将这些视为图中的边:如果您知道对象 x 比较小于对象 y，那么您可以绘制从 x 到 y 的边。

假设比较的结果是一致的——也就是说，你没有任何循环——你应该有一个有向无环图。

想想如果你对这个 DAG 进行拓扑排序会发生什么。您最终得到的是与所有约束一致的一种可能的值排序。这样做的原因是，在拓扑排序中，如果存在从 y 到 x 的任何可传递边系列，则不会将元素 x 放在元素 y 之前，并且如果存在从 y 到 x 的可传递边系列，则有一系列比较传递地表明 y 在 x 之前。

您实际上可以做出更强有力的声明:DAG 的所有拓扑排序的集合恰好是满足所有约束的所有可能排序的集合。我们已经论证过每个拓扑排序都满足所有约束，所以我们现在需要做的就是论证每个满足所有约束的序列都是有效的拓扑排序。这里的论点本质上是，如果你遵守所有约束，你永远不会把序列中的任何元素放在它传递比较小于的东西之前，所以你永远不会把序列中的任何元素放在有路径的东西之前。

这为我们提供了一个很好的解决问题的方法:获取以这种方式形成的图，看看它是否恰好具有一个拓扑顺序。如果是这样，那么该顺序就是唯一的排序顺序。如果不是，则有两个或多个顺序。

那么如何最好地解决这个问题呢？好吧，进行拓扑排序的标准算法之一是用入度注释每个节点，然后重复拉出入度为零的节点并调整其后继节点的入度。如果在执行该算法的过程中，在每个阶段都恰好有一个入度为零的节点，则 DAG 具有恰好一个拓扑排序，因为在这种情况下拓扑排序是强制的。

通过正确的设置和数据结构，您可以实现它以在时间 O(n + m) 内运行，其中 n 是节点数，m 是约束数。我会将这些细节作为众所周知的练习留给读者。 :-)