scala - 使用严格的函数编程从坐姿生成DAG

这是我的问题：我有一个序列S（（非空但可能不不同）集合s_i，并且对于每个s_i，需要知道S（i≠j）中有多少个集合s_j是s_i的子集。我还需要提高性能：一旦有了所有计数，就可以用s_i的某个子集替换一组s_i并逐步更新计数。使用纯功能代码执行所有这些操作将是一个巨大的优势（我在Scala中使用代码）。由于集合包含是部分排序，我认为解决我的问题的最佳方法是构建一个DAG，该DAG表示集合的Hasse图，边表示包含，并将整数值连接到每个节点上，以表示大小节点加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的最后一个是：在DAG中找到v的所有“根子集” rs_i，即v的子集，以使rs_i的超集都不是v的子集。这可以通过在图上执行搜索（BFS或DFS）来轻松完成（函数，可能不是最优的，甚至是有缺陷的）。构建新节点n_v，其子节点是先前找到的rs_i。现在，让我们找出n_v的附加位置：对于给定的根列表，找出v的超集。如果未找到，则将n_v添加到根中，并从根中删除n_v的子集。否则，对超集的子代递归执行步骤3。我还没有完全实现该算法，但是对于我看似简单的问题，它似乎不必要地绕了圈，也不是最优的。是否有一些更简单的算法可用（Google对此一无所知）？ (adsbygoogle = window.adsbygoogle || []).push({}); 最佳答案 经过一些工作，我终于按照最初的直觉解决了我的问题。收集方法和等级评估存在缺陷，我将尾部递归作为奖励重写了它们。这是我获得的代码：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），因此为结果。 (adsbygoogle = window.adsbygoogle || []).push({});