scala – 使用严格功能的编程从一个poset生成一个DAG

发布时间：2020-12-16 09:03:30 所属栏目：安全来源：网络整理

导读：这是我的问题：我有一个序列S(非空但可能不是不同的)集合s_i,并且对于每个s_i,需要知道S(i≠j)中s_j个集合是s_i的子集. 我还需要增量性能：一旦我有了所有的计数,我可以用s_i的一些子集替换一组s_i,并逐渐更新计数. 使用纯功能代码执行所有这一切将是一个巨

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

我还需要增量性能：一旦我有了所有的计数,我可以用s_i的一些子集替换一组s_i,并逐渐更新计数.

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

由于集合包含是部分排序,我认为解决我的问题的最佳方式是构建一个表示集合的Hasse图的DAG,其中边表示包含,并且将每个节点的整数值加到表示大小的节点下面的sub-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)
    }
}

我很卡在这里最后一个我向DAG添加一个新值v是：

在DAG中找到v的所有“根子集”rs_i,即v的子集,使得rs_i的超集不是v的子集,这可以通过在图上执行搜索(BFS或DFS)来很容易地完成收集功能,可能非最佳或甚至有缺陷).
>构建新节点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,head :: (collected.filter(c => !po.lteq(c.v,head.v))))
      else collect(v,head.child ::: tail,collected)
    }

我现在必须检查一些优化：
? – 在收集子集时切断具有完全不同集合的分支(如Rex Kerr所建议的)
? – 看看按尺寸排序集是否改进了过程(如mitchus所建议的)

以下问题是将add()操作的(最坏情况)复杂性工作.
使用n个集合的数量,d是最大集合的大小,复杂度可能是O(n2d),但是我希望它可以被改进.这是我的推理：如果所有的集合是不同的,DAG将被减少到一个根/叶序列.因此,每当我尝试向数据结构添加一个节点时,我仍然必须检查已经存在的每个节点(在收集和附加过程中).这导致1 2 … n = n(n 1)/ 2∈O(n 2)包含检查.

每个集合包含测试是O(d),因此是结果.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!