在Scala中按部分顺序排序

Question

Scala中的部分排序集合询问如何使用Scala中的PartialOrdering进行排序。注释指出，作者不应该在给出的示例中进行部分排序。我确实需要按部分排序排序——我有一些国家可能是其他国家的飞地，这就引出了部分排序。

那么:给定一个List[T]，其中T扩展了PartialOrdering[T]，是否存在一种根据偏序排序的合理方法?

Answer 1

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

  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。

Answer 2

我不完全确定我理解了这个问题。但也许这种从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实现了稳定排序，因此相等的项不会重新排序。