找到链的比较器

Question

我有一对像的列表

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

我们的想法是对它们进行排序,以便第一个节点的第二个索引与第二个节点的第一个匹配.在该示例中,列表已排序.假设列表始终可以唯一地放入此表单中.该列表永远不会循环.

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

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

x.sort(compare)

假设函数compare返回对应于"更大"和"更小"的两个值中的一个.这是否可能,如果是,它是否依赖于排序算法.

如果不可能,它是否可以通过两次通过(可能使用不同的比较器)或任何固定次数的通过.

我在python中写过这个,但我的问题不是具体的.

Answer 1

一次通过是不可能的,因为您想要的顺序不是严格的部分顺序.具体来说,为了使比较器工作,它需要遵循几个属性:

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]链连接.

对问题进行建模的更好方法是尝试通过图形查找欧拉路径.Eulerian路径是一种跟踪一系列链接的方式,因此您永远不会回溯链接,以便跟踪所有链接.(如果你曾经有过那些"画这个数字而不用回线或捡起你的铅笔"的谜题,那就完全一样了.)在你的情况下,链接是对[a,b]和通过它们的链与欧拉路径相同.幸运的是,有很多好的,有效的算法可以找到欧拉路径,我认为它们正是你在这个背景下寻找的.

希望这可以帮助!