使用 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 不一致，您得到的结果也不一致。

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

但是，如果我们可以假设您避免了循环，那么拓扑排序可能会为您提供更像您正在寻找的结果的东西。基本上，您需要的属性不仅仅是 "put this one before that one if the this one's right point is equal to that one's left point"，而是更像 "put this one before that one if [all that] otherwise we don't have enough information to compare them." sortWith 的东西不够复杂，无法进行拓扑排序。它假定所有元素都可以直接进行有意义的比较。

拓扑排序快速入门http://en.wikipedia.org/wiki/Topological_sorting

Answer 2

如果您查看用于 sortWith 的 Comparator，您会发现：

def sortWith(lt: (A, A) => Boolean): Repr = sorted(Ordering fromLessThan lt)

def fromLessThan[T](cmp: (T, T) => Boolean): Ordering[T] = new Ordering[T] {
    def compare(x: T, y: T) = if (cmp(x, y)) -1 else if (cmp(y, x)) 1 else 0

例如，当基础算法比较 (5,6) 和 (1,2) 时，您的 x._2 == y._1 将首先检查 6 不等于 1 然后2 不等于 5 最后将决定这些元组是否相等。出于这个原因，你应该使用这样的东西：

x._2 <= y._1 // for tuples where _1 < _2
x._2 >= y._1 // for tuples where _1 > _2

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

Sort a list of chained tuples with sortWith

sorting

scala

list

higher-order-functions