Сортировка списка цепочечных кортежей с 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 несовместим, и вы получаете непоследовательные результаты.

Прежде чем вы сможете найти обобщенное решение, вам придется иметь дело с некоторыми глубокими проблемами с проблемным пространством. То, что вы в основном пытаетесь сделать, это сортировать произвольный направленный граф. Это означает, что у него могут быть циклы, отключенные подграфы и всевозможные другие вещи, которые исключают какое-либо очевидное полное упорядочение.

Но если мы можем предположить, что вы избегаете циклов, то топологическая сортировка может дать вам нечто большее, чем результаты, которые вы ищете. В принципе, вам нужно не просто «поставить это перед тем, если правая точка этого права равна той, что находится в левой точке», а что-то более похожее на «поставить это перед этим, если [все это] в противном случае мы надеемся «У них достаточно информации для их сравнения». sortWith недостаточно сложный, чтобы сделать топологический вид. Он предполагает, что все элементы можно сравнить непосредственно осмысленно.

Быстрое введение в топологической сортировки http://en.wikipedia.org/wiki/Topological_sorting

Answer 2

Если посмотреть на Comparator, который используется для sortWith вы найдете:

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 

Так, например с вашим x._2 == y._1, когда основной алгоритм сравнивает (5,6) и (1,2) он сначала проверит, что 6 не будет равен 1, тогда 2 не будет равен 5 и, наконец, решит, что эти tup les равны. По этой причине вы должны использовать примерно следующее:

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