4

我有一个配对列表，例如

[[4,1],[1,2],[2,3]]

这个想法是对它们进行排序，以便第一个节点的第二个索引与第二个节点的第一个索引匹配。在示例中，列表已排序。假定列表总是可以唯一地放入这种形式中。该列表从不循环。

现在，如果可能的话，我想要一个compare可以通过以下方式获得此表格的比较器：

x = [[4,1],[1,2],[2,3]]

x.sort(compare)

假设该函数compare返回对应于“更大”和“更小”的两个值之一。这是否可能，如果是，是否取决于排序算法。

如果不可能，是否可以通过两次（可能使用不同的比较器）或任何固定数量的通过。

我已经用 python 编写了这个，但我的问题并不具体。

4

1 回答 1

8

不可能一次性完成，因为您想要的排序不是严格的偏序。具体来说，为了让比较器工作，它需要遵守几个属性：

  1. 非自反性：一个元素永远不会比它自己少。
  2. 不对称：如果 a 比较小于 b，则 b 不比较小于 a。
  3. 传递性：如果 a 比较小于 b，b 比较小于 c，则 c 不比较小于 a。

在您的情况下，所有这三个属性都被违反：

  1. [1, 1] 比较小于自身，因为您可以链接 [1, 1], [1, 1]。
  2. 两个元素可以相互链接：[1, 4] 链与 [4, 1] 和 [4, 1] 链与 [1, 4]。
  3. 传递性不成立：[1, 2] 链与 [2, 3] 和 [2, 3] 链与 [3, 4]，但 [1, 2] 不与 [3, 4] 链。

为您的问题建模的更好方法是尝试通过图形找到欧拉路径。欧拉路径是一种遵循一系列链接的方式，这样您就永远不会回溯链接，并且所有链接都被追踪出来。（如果您曾经遇到过“在不回溯线或拿起铅笔的情况下绘制此图形”的难题，那几乎是相同的想法。）在您的情况下，链接是对 [a, b] 和通过它们的链与欧拉路径相同。幸运的是，有许多好的、有效的算法可以找到欧拉路径，我认为它们正是您在这种情况下所要寻找的。

希望这可以帮助！

于 2013-06-14T02:16:33.960 回答