13

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

我还需要增量性能：一旦我有了所有的计数，我可以用 s_i 的某个子集替换一组 s_i 并逐步更新计数。

使用纯函数式代码执行所有这些将是一个巨大的优势（我在 Scala 中编写代码）。

由于集合包含是部分排序，我认为解决我的问题的最佳方法是构建一个 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)
    }
}

我被困在这里了。最后我想为 DAG 添加一个新值 v 是：

  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 步。

我还没有完全实现这个算法，但对于我看似简单的问题来说，它似乎是不必要的迂回和非最优的。是否有一些更简单的算法可用（谷歌对此一无所知）？

4

2 回答 2

2

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

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 建议的那样） - 查看按大小对集合进行排序是否改进了过程（如 michus 建议的那样）

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

每个集合包含测试都是 O(d)，因此结果。

于 2012-01-19T14:33:31.617 回答
0

假设您的 DAGG包含v每个集合的节点，具有属性v.s（集合）和v.count（集合的实例数），包括一个节点G.root（G.root.s = union of all sets如果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))))

但在我看来，出于性能原因，最好放弃这种纯粹的功能解决方案......它在列表和树上运行良好，但除此之外，事情变得艰难。

于 2012-01-17T15:41:03.547 回答