13

ここに私の問題があります：私は（空ではないがおそらく明確ではない）セットs_iのシーケンスSを持っており、各s_iについて、S内のセットs_j（i≠j）がs_iのサブセットである数を知る必要があります。

また、インクリメンタル パフォーマンスも必要です。すべてのカウントを取得したら、1 つのセット s_i を s_i のサブセットに置き換えて、カウントをインクリメンタルに更新します。

純粋に機能的なコードを使用してこれらすべてを実行すると、大きなプラスになります (私は Scala でコーディングしています)。

セットの包含は半順序付けであるため、私の問題を解決する最善の方法は、セットのハッセ図を表す 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 を追加するために最後に思いついたのは次のとおりです。

  1. DAG 内の v のすべての「ルート サブセット」rs_i、つまり、rs_i のスーパーセットが v のサブセットではないような v のサブセットを見つけます。これは、グラフで検索 (BFS または DFS) を実行することによって非常に簡単に行うことができます (collect関数、おそらく最適ではないか、欠陥がある可能性さえあります）。
  2. 新しいノード n_v を構築します。その子ノードは以前に見つかった rs_i です。
  3. 次に、n_v をどこに付けるかを調べましょう: 与えられたルートのリストについて、v のスーパーセットを見つけます。何も見つからない場合は、ルートに n_v を追加し、ルートから n_v のサブセットを削除します。それ以外の場合は、スーパーセットの子に対してステップ 3 を再帰的に実行します。

私はまだこのアルゴリズムを完全に実装していませんが、明らかに単純な問題に対して不必要に回旋しており、最適ではないようです。利用可能な単純なアルゴリズムはありますか (Google はこれについて無知でした)。

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 が示唆したように) - サイズでセットをソートするとプロセスが改善されるかどうかを確認します (mitchus が示唆したように)

次の問題は、(最悪の場合) 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

DAGに、属性(セット) と(セットのインスタンスの数) を持つ各セットGのノードが含まれているとします。これには、(このセットがコレクション内で発生しない場合) を持つノードが含まれます。vv.sv.countG.rootG.root.s = union of all setsG.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 に答える