Как заказать список кортежей целых чисел в Scala

Question

У меня есть список кортежей целых

List[(Int, Int, Int)] = List((2,1,3), (4,2,6), (4,7,9), (6,3,9), (6,7,11), 
      (6,17,19), (8,4,12), (8,14,18), (10,5,15), (12,1,17), (12,6,18)) 

и я хотел бы, чтобы отсортировать их, увеличивая гр, но если есть кортежи Withe то же самое с, то заказывать их, увеличивая b. Итак, в этом случае случай (4,7,9), (6,3,9) я хотел бы (6,3,9), (4,7,9).

К сожалению, я не работал.

 def order(k: List[(Int, Int, Int)]) = { 
     var t = List[Int]() 
     if (k.map(_._3) == t) { 
      k.sortBy(_._2) 
      t = k.map(_._3) 
      k 
     } else { 
      k.sortBy(_._3) 
      t = k.map(_._3) 
      k 
     } 
    } 

Заранее благодарю вас!

Answer 1

Простым и удивительно быстрым подходом является использование стабильного алгоритма сортировки и сортировка сначала по первому компоненту, затем по второму, затем по третьему. Поскольку вы отсортированы последним по третьему компоненту, это будет доминирующим. При использовании стабильного рода, объекты, привязанные в последнем компоненте будут упорядочены по предыдущему:

Sorting.stableSort(k, (x, y) => x._1 < y._1) 
Sorting.stableSort(k, (x, y) => x._2 < y._2) 
Sorting.stableSort(k, (x, y) => x._3 < y._3) 

или, что эквивалентно (но, вероятно, более дорогим, так как она строит последовательность клавиш):

Sorting.stableSort(k, x => x._1) 
Sorting.stableSort(k, x => x._2) 
Sorting.stableSort(k, x => x._3) 

(при условии, что Seq.sortBy не является стабильным.)

в качестве альтернативы (и это более классический и очевидный подход), написать компаратор (Ordering), который использует третий компонент если отличается, затем второй , если он отличается и, наконец, первым. Это, вероятно, не очень «scalish», но это имхо очень чисто и понятно:

val result = intOrdering.compare(x._3, y._3) 
if (result == 0) result = intOrdering.compare(x._2, y._2) 
if (result == 0) result = intOrdering.compare(x._1, y._1) 
result 

снова, вы можете также использовать ключевую функцию (но это нужно будет 2x больше памяти):

k.sortBy(x => (x._3, x._2, x._1)) 

Answer 2

Вы можете предоставить свои собственные Ordering[Tuple3[Int, Int, Int]], а затем просто используйте sorted на List. Например, вот что-то вроде стандарта Ordering на Tuple3, за исключением того, что сортировка по ординатам отменена. Для любых (a, b, c), c имеет более высокий приоритет, чем b, а b имеет более высокий приоритет, чем a. Вы действительно не упоминали, как обращаться с a, поэтому, если вас это не волнует, вы можете просто удалить соответствующие строки.

val list = List((2,1,3), (4,2,6), (4,7,9), (6,3,9), (6,7,11), (6,17,19), (8,4,12), (8,14,18), (10,5,15), (12,1,17), (12,6,18)) 

implicit def t3Ordering(implicit intOrdering: Ordering[Int]) = new Ordering[Tuple3[Int, Int, Int]] { 
    def compare(x: (Int, Int, Int), y: (Int, Int, Int)): Int = { 
     val compare3 = intOrdering.compare(x._3, y._3) 
     if (compare3 != 0) return compare3 
     val compare2 = intOrdering.compare(x._2, y._2) 
     if (compare2 != 0) return compare2 
     val compare1 = intOrdering.compare(x._1, y._1) 
     if (compare1 != 0) return compare1 
     0 
    } 
} 

scala> list.sorted 
res0: List[(Int, Int, Int)] = List((2,1,3), (4,2,6), (6,3,9), (4,7,9), (6,7,11), (8,4,12), (10,5,15), (12,1,17), (12,6,18), (8,14,18), (6,17,19)) 

Или в более общем плане обратной сортировки, основанный на Tuple ординат (для Tuple3):

implicit def t3Ordering[T1, T2, T3](implicit ord1: Ordering[T1], ord2: Ordering[T2], ord3: Ordering[T3]) = 
    new Ordering[Tuple3[T1, T2, T3]] { 
    def compare(x: (T1, T2, T3), y: (T1, T2, T3)): Int = { 
     val compare3 = ord3.compare(x._3, y._3) 
     if (compare3 != 0) return compare3 
     val compare2 = ord2.compare(x._2, y._2) 
     if (compare2 != 0) return compare2 
     val compare1 = ord1.compare(x._1, y._1) 
     if (compare1 != 0) return compare1 
     0 
    } 
    } 

На основе standard library Ordering.

Answer 3

Кажется, что

k.sortBy(x => (x._3 , x._2)) 

делает работу и возвращает

List[(Int, Int, Int)] = List((2,1,3), (4,2,6), (6,3,9), (4,7,9), (6,7,11), 
      (8,4,12), (10,5,15), (12,1,17), (12,6,18), (8,14,18), (6,17,19)) 

, который также работает (12,6,18), (8,14,18)