Tuple2의리스트가 주어진 sortWith

Question

으로 연결된 튜플 목록을 정렬합니다. 둘 중 하나의 두 번째 요소가 다음 요소의 첫 번째 요소가되도록 정렬하려고합니다. 나는 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는 토폴로지 정렬을 수행 할만큼 정교하지 않습니다. 모든 요소를 ​​직접적으로 의미있게 비교할 수 있다고 가정합니다.

빠른 소개는 sortWith에 사용되는 당신이 찾을 수 Comparator 보면 http://en.wikipedia.org/wiki/Topological_sorting

Answer 2

정렬 위상합니다 : 예를 들어 너무

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 레는 동등하다. 따라서 다음과 같이 사용해야합니다.

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