scala - 使用严格的函数式编程从偏序集生成 DAG

Question

这是我的问题:我有一个(非空但可能不明显)集合 s_i 的序列 S，并且对于每个 s_i，需要知道 S(i ≠ j)中有多少个集合 s_j 是 s_i 的子集。

我还需要增加性能:一旦我拥有所有计数，我可以用 s_i 的某个子集替换一组 s_i 并逐步更新计数。

使用纯函数代码执行所有这些将是一个巨大的优势(我在 Scala 中编写代码)。

由于集合包含是偏序，我认为解决我的问题的最佳方法是构建一个 DAG 来表示集合的哈斯图，边表示包含，并将整数值连接到每个节点，表示集合的大小节点下方的 sub-dag 加 1。然而，我已经被困了好几天，试图开发从偏序构建哈斯图的算法(我们不要谈论增量!)，尽管我认为这会是一些标准本科教材。

这是我的数据结构:

case class HNode[A] (
  val v: A,
  val child: List[HNode[A]]) {
  val rank = 1 + child.map(_.rank).sum
}

我的 DAG 由根列表和一些偏序定义:

class Hasse[A](val po: PartialOrdering[A], val roots: List[HNode[A]]) {
  def +(v: A): Hasse[A] = new Hasse[A](po, add(v, roots))

  private def collect(v: A, roots: List[HNode[A]], collected: List[HNode[A]]): List[HNode[A]] =
    if (roots == Nil) collected
    else {
      val (subsets, remaining) = roots.partition(r => po.lteq(r.v, v))
      collect(v, remaining.map(_.child).flatten, subsets.filter(r => !collected.exists(c => po.lteq(r.v, c.v))) ::: collected)
    }
}

我很困在这里。最后我想为 DAG 添加一个新值 v 是:

在 DAG 中找到 v 的所有“根子集”rs_i，即 v 的子集，使得 rs_i 的超集都不是 v 的子集。这可以通过在图上执行搜索(BFS 或 DFS)来轻松完成( collect 函数，可能不是最佳的甚至有缺陷)。

构建新节点 n_v，其子节点是先前找到的 rs_i。

现在，让我们找出应该附加 n_v 的位置:对于给定的根列表，找出 v 的超集。如果没有找到，则将 n_v 添加到根并从根中删除 n_v 的子集。否则，对超集的子集递归执行第 3 步。

我还没有完全实现这个算法，但对于我这个看似简单的问题来说，它似乎是不必要的复杂和非最优的。是否有一些更简单的算法可用(谷歌对此一无所知)？

Answer 1

经过一番努力，我终于按照我最初的直觉解决了我的问题。收集方法和等级评估有缺陷，我用尾递归重写它们作为奖励。这是我获得的代码:

final case class HNode[A](
  val v: A,
  val child: List[HNode[A]]) {
  val rank: Int = 1 + count(child, Set.empty)

  @tailrec
  private def count(stack: List[HNode[A]], c: Set[HNode[A]]): Int =
    if (stack == Nil) c.size
    else {
      val head :: rem = stack
      if (c(head)) count(rem, c)
      else count(head.child ::: rem, c + head)
    }
}

// ...

  private def add(v: A, roots: List[HNode[A]]): List[HNode[A]] = {
    val newNode = HNode(v, collect(v, roots, Nil))
    attach(newNode, roots)
  }

  private def attach(n: HNode[A], roots: List[HNode[A]]): List[HNode[A]] =
    if (roots.contains(n)) roots
    else {
      val (supersets, remaining) = roots.partition { r =>
        // Strict superset to avoid creating cycles in case of equal elements
        po.tryCompare(n.v, r.v) == Some(-1)
      }
      if (supersets.isEmpty) n :: remaining.filter(r => !po.lteq(r.v, n.v))
      else {
        supersets.map(s => HNode(s.v, attach(n, s.child))) ::: remaining
      }
    }

  @tailrec
  private def collect(v: A, stack: List[HNode[A]], collected: List[HNode[A]]): List[HNode[A]] =
    if (stack == Nil) collected
    else {
      val head :: tail = stack

      if (collected.exists(c => po.lteq(head.v, c.v))) collect(v, tail, collected)
      else if (po.lteq(head.v, v)) collect(v, tail, head :: (collected.filter(c => !po.lteq(c.v, head.v))))
      else collect(v, head.child ::: tail, collected)
    }

我现在必须检查一些优化:
- 在收集子集时用完全不同的集合切断分支(如 Rex Kerr 建议的那样)
- 查看按大小对集合进行排序是否可以改进过程(如米丘斯建议的那样)

下面的问题是解决 add() 操作的(最坏情况)复杂性。
n 是集合的数量，d 是最大集合的大小，复杂度可能是 O(n²d)，但我希望它可以改进。这是我的推理:如果所有集合都是不同的，则 DAG 将减少为一系列根/叶。因此，每次我尝试向数据结构添加节点时，我仍然必须检查是否包含每个已经存在的节点(在收集和附加过程中)。这导致 1 + 2 + … + n = n(n+1)/2 ∈ O(n²) 包含检查。

每个集合包含测试都是 O(d)，因此结果。