list - 使用 sortWith 对链式元组列表进行排序

Question

给定 Tuple2 的列表，我想对它们进行排序，以便其中一个的第二个元素是下一个的第一个元素。我试过用 sortWith 来做，但它在某些情况下有效，但在其他情况下无效。谁能看出我哪里搞砸了？

Welcome to Scala version 2.10.3-20130923-e2fec6b28dfd73482945ffab85d9b582d0cb9f17 (OpenJDK 64-Bit Server VM, Java 1.7.0_71).
Type in expressions to have them evaluated.
Type :help for more information.

scala> val l = List((2,3),(1,2),(3,4))
l: List[(Int, Int)] = List((2,3), (1,2), (3,4))

scala> l.sortWith((x,y) => x._2 == y._1)
res0: List[(Int, Int)] = List((1,2), (2,3), (3,4))

scala> val m = List((2,3),(5,6),(1,2),(3,4),(4,5))
m: List[(Int, Int)] = List((2,3), (5,6), (1,2), (3,4), (4,5))

scala> m.sortWith((x,y) => x._2 == y._1)
res1: List[(Int, Int)] = List((2,3), (5,6), (1,2), (3,4), (4,5))

非常感谢

Answer 1

sortWith 基本上说，如果条件为真，那么第一个参数应该在第二个参数之前出现，如果条件为假，那么它们应该以另一种方式排序。对于绝大多数比较，您的 sortWith 条件返回 false，这会将事情推向右侧，即使之前的比较表明某些事情应该更靠左。

简而言之，您的 sortWith 不一致，您得到的结果也不一致。

在提出通用解决方案之前，您必须处理问题空间中的一些深层问题。您基本上要做的是对任意有向图进行排序。这意味着它可以有循环、断开连接的子图和各种其他排除任何明显总排序的事物。

但是，如果我们可以假设您可以避免循环，那么拓扑排序可能会为您提供更接近您正在寻找的结果的结果。基本上你需要的属性不仅仅是“如果这个人的右点等于那个人的左点，就把这个放在那个之前”，而是更像是“如果 [all that] 否则我们不这样做，把这个放在那个之前没有足够的信息来比较它们。” sortWith 不够复杂，无法进行拓扑排序。它假设所有元素都可以直接进行有意义的比较。

拓扑排序简介 http://en.wikipedia.org/wiki/Topological_sorting