scala - 在Scala中按偏序排序

Question

在 Scala 中对集合进行部分排序询问如何在 Scala 中按 PartialOrdering 进行排序。评论指出作者不应该在给出的示例中进行部分排序。我确实需要按偏序排序——我有可能是其他国家飞地的国家，这会导致偏序。

那么：给定 a List[T], where Textends PartialOrdering[T], 是否有一种根据偏序排序的合理方式？

Answer 1

我不完全确定我理解这个问题。但也许这种从PartialOrdering到 的转换Ordering有效：

def sortWithPartialSort[A : PartialOrdering](list: Seq[A]): Seq[A] = {
  list.sorted(
    Ordering.fromLessThan { case (x,y) =>
      implicitly[PartialOrdering[A]].lt(x, y)
    }
  )
}

注意PartialOrdering.lt定义为：

def lt(x: T, y: T): Boolean = lteq(x, y) && !equiv(x, y)
def equiv(x: T, y: T): Boolean = lteq(x,y) && lteq(y,x)

所以如果我理解正确的话，lteq你可以定义一个完整的顺序。

另请注意，它Seq.sorted实现了稳定的排序，因此不会重新排序相等的项目。

Answer 2

我自己写了一个合适的排序。像这样的案例总是让我觉得我错过了一个标准库函数。

  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不多。