algorithm - 如何使用 PartialOrdering 对集合进行排序？

Question

我需要订购一组信封。每个信封都用它的高度和宽度来描述。信封 1 小于信封 2，如果它可以插入信封 2。如果 envelope1 不能插入到 envelope2 中，反之亦然，则它们无法进行比较。

我如何在 Scala 中订购这些信封？我在互联网上找不到任何相关信息。

这是我的一些代码:

object EnvelopeOrdering extends PartialOrdering[(Int, Int)] {
  override def tryCompare(x: (Int, Int), y: (Int, Int)): Option[Int] = {
    if (x._1 < y._1 && x._2 < y._2) return Some(1)
    if (x._1 > y._1 && x._2 > y._2) return Some(-1)
    if (x._1 == y._1 && x._2 == y._2) return Some(0)
    None
  }

  override def lteq(x: (Int, Int), y: (Int, Int)): Boolean = x._1 < y._1 && x._2 < y._2
}

Answer 1

您感兴趣的是topological sort并且有一种经典算法可以按照边数的顺序复杂地执行它。在您的情况下，当且仅当第一个信封较小时(并且边缘应从较小的指向较大的)，您将在两个信封之间有一条边。