使用严格的函数式编程从poset生成DAG

Question

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

我还需要增量性能:一旦我完成所有计数,我可以用s_i的某个子集替换一组s_i并逐步更新计数.

使用纯功能代码执行所有这些将是一个巨大的优势(我在Scala中的代码).

由于set包含是一个部分排序,我认为解决我的问题的最好方法是构建一个DAG,它表示集合的Hasse图,边表示包含,并将一个整数值连接到表示大小的每个节点节点下方的子d加1.但是,我已经被困了好几天试图开发从部分排序构建Hasse图的算法(让我们不谈增量!),即使我认为它会是一些标准本科教材.

这是我的数据结构:

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:

1. 找到DAG中v的所有"根子集"rs_i,即v的子集,使得rs_i的超集不是v的子集.这可以通过在图上执行搜索(BFS或DFS)非常容易地完成(collect函数) ,可能是非最佳的甚至是有缺陷的).
2. 构建新节点n_v,其子节点是先前找到的rs_i.
3. 现在,让我们找出应该附加n_v的位置:对于给定的根列表,找出v的超集.如果没有找到,则将n_v添加到根并从根中删除n_v的子集.否则,以递归方式对超集的子节点执行步骤3.

我还没有完全实现这个算法,但是对于我看似简单的问题,它看起来似乎是不完整的,并且不是最优的.是否有一些更简单的算法可用(谷歌对此无能为力)？

Answer 1

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

\n\n

final case class HNode[A](\n  val v: A,\n  val child: List[HNode[A]]) {\n  val rank: Int = 1 + count(child, Set.empty)\n\n  @tailrec\n  private def count(stack: List[HNode[A]], c: Set[HNode[A]]): Int =\n    if (stack == Nil) c.size\n    else {\n      val head :: rem = stack\n      if (c(head)) count(rem, c)\n      else count(head.child ::: rem, c + head)\n    }\n}\n\n// ...\n\n  private def add(v: A, roots: List[HNode[A]]): List[HNode[A]] = {\n    val newNode = HNode(v, collect(v, roots, Nil))\n    attach(newNode, roots)\n  }\n\n  private def attach(n: HNode[A], roots: List[HNode[A]]): List[HNode[A]] =\n    if (roots.contains(n)) roots\n    else {\n      val (supersets, remaining) = roots.partition { r =>\n        // Strict superset to avoid creating cycles in case of equal elements\n        po.tryCompare(n.v, r.v) == Some(-1)\n      }\n      if (supersets.isEmpty) n :: remaining.filter(r => !po.lteq(r.v, n.v))\n      else {\n        supersets.map(s => HNode(s.v, attach(n, s.child))) ::: remaining\n      }\n    }\n\n  @tailrec\n  private def collect(v: A, stack: List[HNode[A]], collected: List[HNode[A]]): List[HNode[A]] =\n    if (stack == Nil) collected\n    else {\n      val head :: tail = stack\n\n      if (collected.exists(c => po.lteq(head.v, c.v))) collect(v, tail, collected)\n      else if (po.lteq(head.v, v)) collect(v, tail, head :: (collected.filter(c => !po.lteq(c.v, head.v))))\n      else collect(v, head.child ::: tail, collected)\n    }\n

\n\n

我现在必须检查一些优化：\n - 在收集子集时切断具有完全不同集的分支（如 Rex Kerr 建议的那样）\n - 看看按大小对集进行排序是否可以改进过程（如 mitchus 建议的那样）

\n\n

以下问题是解决 add() 操作的（最坏情况）复杂性。\n如果集合数为 n，最大集合的大小为 d，则复杂性可能为 O(n\xc2\xb2d) ，但希望可以完善一下。我的推理是这样的：如果所有集合都是不同的，那么 DAG 将被简化为根/叶的序列。因此，每次我尝试将节点添加到数据结构时，我仍然必须检查是否包含已存在的每个节点（在收集和附加过程中）。这导致 1 + 2 + \xe2\x80\xa6 + n = n(n+1)/2 \xe2\x88\x88 O(n\xc2\xb2) 包含检查。

\n\n

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

\n