Sorting a list of chained tuples with sortWith
given the Tuple2 list, I want to sort them so that the second element of one is the first element of the next. I've tried doing this with sortWith, but it works in some cases but not others. Can anyone see where I am confused?
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))
Many thanks
source to share
sortWith basically says that if the condition is true then the first arg should come somewhere before the second arg and if the condition is false then they need to be ordered in a different way. For the vast majority of comparisons, your sortWith condition returns false, which pushes things to the right, even after the previous comparison says something must go more left.
In short, your sortWith is inconsistent and you get conflicting results.
Before you can find a generalized solution, you will have to deal with some serious problem space issues. What you are basically trying to do is sort an arbitrary directed graph. This means it can have loops, disconnected subgraphs, and all sorts of other things that rule out any obvious complete ordering.
But if we can assume that you are avoiding loops, then topological sorting may give you more than the results you are looking for. Basically, you don't just need to "put this in front if this right point equals this left point", but something more like "put this in front of this if [all this] otherwise we hope" They have enough information to compare them. "sortWith is not complex enough to make a topological view. It assumes that all elements can be directly compared.
A quick introduction to topological sorting http://en.wikipedia.org/wiki/Topological_sorting
source to share
If you look Comparator
at which one is used for sortWith
, you will find:
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
so with yours, for example, x._2 == y._1
when the underlying algorithm compares (5,6)
and (1,2)
, it first checks what is 6
not equal 1
, then 2
not equal 5
and finally will decide that these tuples are equal. For this reason, you should use something like this:
x._2 <= y._1 // for tuples where _1 < _2
x._2 >= y._1 // for tuples where _1 > _2
source to share