Сортировка по частичному порядку в Scala

Частичная сортировка коллекций в Scala спрашивает, как сортировать по PartialOrdering в Scala. В комментариях указано, что автор не должен частично сортировать в приведенном примере. Мне действительно нужно сортировать по частичному порядку — у меня есть страны, которые могут быть анклавами других стран, и это приводит к частичному порядку.

Итак: учитывая List[T], где T расширяет PartialOrdering[T], есть ли разумный способ сортировки в соответствии с частичным порядком?


sorting scala partial-ordering
person Mohan    schedule 04.11.2016    source источник
comment
Каким должен быть окончательный список?   -  person pamu    schedule 04.11.2016
comment
Можете привести пример того, каким должен быть начальный и окончательный список?   -  person pamu    schedule 04.11.2016
comment
Помогает ли это: stackoverflow.com/questions/4620100/partial-order-sorting   -  person wks    schedule 04.11.2016

Ответы (1)


arrow_upward
0
arrow_downward

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

  def sortByPartialOrdering[T](ts: Array[T], lessThan: (T, T) => Boolean): ListBuffer[T] = {
    val len = ts.size
    val visited = Array.fill[Boolean](len)(false)
    val postOrder = ListBuffer.empty[Int]

    def visit(n: Int): Unit = {
      visited(n) = true
      for (i <- 0 until len)
        if (!visited(i) && lessThan(ts(i), ts(n)))
          visit(i)
      postOrder += n
    }

    for (i <- 0 until len)
      if (!visited(i))
        visit(i)

    assert(postOrder.size == len)

    postOrder map ts
  }

Комментарии/улучшения приветствуются - я не так много пишу на Scala.

person Mohan    schedule 04.11.2016