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

Question

这是我的问题：我有一个由非空但可能不相同的集合$s_i$组成的序列$S$，对于每个$s_i$，需要知道在$S$中有多少个集合$s_j$（$i≠j$）是$s_i$的子集。

我还需要实现增量性能：一旦我得到所有计数，我可以通过某些$s_i$的子集替换它，并递增更新计数。

使用纯函数式代码执行所有这些操作将是巨大的加分项（我用Scala编写代码）。

由于集合包含是偏序关系，我认为解决我的问题的最佳方法是构建一个DAG，该DAG表示集合的Hasse图，具有表示包含的边，并在每个节点上连接一个整数值，该值表示下面子DAG的大小加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)
    }
}

我卡在这里了。我目前为止最后想到的是要将新值v添加到DAG中：

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。

我还没有完全实现这个算法，但它似乎对我的明显简单问题来说过于复杂和非最优了。是否有某种更简单的可用算法（Google对此毫无头绪）？

- scand1sk

---

那个算法对我来说似乎非常简单，没有不必要的复杂性。问题到底是什么？它的Scala代码几乎不会比你的描述更长。（虽然我认为你甚至还没有完全描述清楚。） - Rex Kerr

自从我开始接触函数式编程（大约6个月前），处理递归数据结构时，我已经习惯了使用一行代码。开发一个不在单个递归调用中的三步算法感觉很奇怪（步骤1与步骤3不连续）。此外，这个算法检查子集两次（步骤1和3），这感觉不对。 - scand1sk

作为参考，最近我实现了一个二项堆，感觉要简单得多（尽管可能是因为算法定义得更好）。 - scand1sk

实际上，在之前的错误分析中，我设法完成了它，我发现部分排序会导致一棵树。我以为用有向无环图(DAG)代替树会很容易，但是我错了：部分排序意味着我的新元素的子集可以出现在DAG的任何位置，而不仅仅是在一个特定的子树中。 - scand1sk

是的，我发现了这一点，但是我必须放弃我的PartialOrdering泛化（或者扩展PartialOrdering以添加一些“不相交”的方法）。 - scand1sk

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所建议的） - 查看按大小排序集合是否可以改善过程（如mitchus所建议的）

以下问题是计算add()操作的最坏情况复杂度。 假设n为集合数量，d为最大集合的大小，则复杂度可能为O(n²d)，但我希望它能被优化。我的推理如下：如果所有集合都不同，则DAG将缩减为根/叶的序列。因此，每次尝试向数据结构中添加节点时，我仍然必须检查每个已经存在的节点是否包含该节点（在collect和attach过程中都是如此）。这导致了1 + 2 + … + n = n(n+1)/2 ∈ O(n²)个包含检查。

每个集合包含测试为O(d)，因此得出上述结果。

- scand1sk

---

一些使用随机生成集合的简单基准测试似乎证实了在平均情况下，复杂度仍然是O(n²d)。 - scand1sk

上述代码存在一个bug：attach过程中的HNodes创建将DAG中的节点分裂。我正在修复这个问题。 - scand1sk

Answer 2

假设您的DAG G包含每个集合的节点v，具有属性v.s（集合）和v.count（集合实例数），包括一个带有G.root.s = union of all sets的节点G.root（如果此集合从未出现在您的集合中，则G.root.count = 0）。

然后，要计算s的不同子集的数量，您可以执行以下操作（使用Scala、Python和伪代码的混合语言）：

sum(apply(lambda x: x.count, get_subsets(s, G.root)))

在哪里

get_subsets(s, v) :
   if(v.s is not a subset of s, {}, 
      union({v} :: apply(v.children, lambda x: get_subsets(s, x))))

在我看来，出于性能的考虑，你最好放弃这种纯函数式的解决方案...它对于列表和树结构来说效果很好，但是超出这个范围就会变得棘手。

- mitchus

---

这个答案假设DAG存在，是吗？我的第一个问题是从部分顺序生成DAG。经过进一步的研究，似乎我想计算传递闭包的反向，并且可能与拓扑排序有关。 - scand1sk

实际上，我只有部分顺序。在我的问题根源处，我没有v.children。我希望尽可能高效地找到子元素（希望比O(n²)更好）。 - scand1sk

确实，我这里假设DAG已经存在。为了构建它，首先你可以按大小对集合进行排序；子集总是比超集小。接下来，我会建立一个人工根节点，其集合为所有集合的并集。然后想法就成了，按减小的顺序取集合，为其创建一个节点，并决定哪些是其“最小的”超集；你要链接到那些而且只有那些。从根节点开始，迭代地进入所有超集节点，直到到达那些“最小的”超集；每次到达这样的超集时，添加一个链接。 - mitchus