gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-03 23:58:15 25 4
gpt4 key购买 nike

这是我的问题:我有一个(非空但可能不明显)集合 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 步。

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

    最佳答案

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

    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/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com