这是我的问题:我有一个(非空但可能不明显)集合 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 是:
collect
函数,可能不是最佳的甚至有缺陷)。 我还没有完全实现这个算法,但对于我这个看似简单的问题来说,它似乎是不必要的复杂和非最优的。是否有一些更简单的算法可用(谷歌对此一无所知)?
最佳答案
经过一番努力,我终于按照我最初的直觉解决了我的问题。收集方法和等级评估有缺陷,我用尾递归重写它们作为奖励。这是我获得的代码:
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),因此结果。
关于scala - 使用严格的函数式编程从偏序集生成 DAG,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8838779/