厳しい機能的なプログラミングを使用してPosetからDAGを生成する

Question

私の問題は次のとおりです。私は（空ではないがおそらく明確ではない）S_Iのシーケンスsを持っています。S_Iごとに、s（i≠j）のS_Jの数がS_Iのサブセットであるかを知る必要があります。

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

純粋に機能的なコードを使用してこれらすべてを実行することは大きなプラスです（私はSCALAでコードします）。

セットインクルージョンは部分的な順序であるため、私の問題を解決するための最良の方法は、セットのハッセ図を表すDAGを構築することであり、エッジが包含を表し、各ノードのサイズを表す各ノードに整数値を結合することだと思いました。ノードプラス1の下のサブダグ1.しかし、私は部分的な順序付けからハッセ図を構築するアルゴリズムを開発しようとして数日間立ち往生しています（増分について話さないでください！）標準的な学部資料。

これが私のデータ構造です：

case class HNode[A] (
  val v: A,
  val child: List[HNode[A]]) {
  val rank = 1 + child.map(_.rank).sum
}

私のダグは、ルーツのリストといくつかの部分的な順序で定義されています。

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のVのすべての「ルートサブセット」RS_I、つまりVのサブセットを見つけて、RS_IのスーパーセットはVのサブセットではありません。これは、グラフで検索（BFSまたはDFS）を実行することで非常に簡単に実行できます（collect 機能、おそらく最適ではない、または欠陥がある）。
2. 新しいノードN_Vを構築します。その子供は以前に発見されたRS_Iです。
3. 次に、N_Vを添付する場所を確認しましょう。根の特定のリストについては、vのスーパーセットを見つけてください。何も見つかった場合は、根にN_Vを追加し、根からN_Vのサブセットを削除します。そうでなければ、スーパーセットの子供を再帰的にステップ3を実行します。

私はまだこのアルゴリズムを完全に実装していませんが、明らかに単純な問題については、間違いなく回転していないようです。簡単なアルゴリズムが利用可能です（Googleはこれについて無知でした）？

Answer 1

いくつかの作業の後、私はついに私の最初の直感に続いて私の問題を解決することになりました。収集方法とランク評価には欠陥があり、ボーナスとしてテールリクールでそれらを書き直しました。これが私が取得したコードです：

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がセットの数と最大のセットのサイズである場合、複雑さはおそらくo（n²d）になりますが、改良できることを願っています。私の推論は次のとおりです。すべてのセットが異なる場合、DAGは根/葉のシーケンスに縮小されます。したがって、データ構造にノードを追加しようとするたびに、既に存在する各ノードに含めることを確認する必要があります（コレクションと添付の手順の両方）。これにより、1 + 2 +… + n = n（n + 1）/2∈O（n²）包含チェックにつながります。

各セットインクルージョンテストはo（d）であるため、結果が得られます。

Answer 2

あなたのダグを想定してください G ノードが含まれています v 各セットに対して、属性を備えています v.s （セット）と v.count （セットのインスタンス数）、ノードを含む G.root と G.root.s = union of all sets （どこ G.root.count=0 このセットがコレクションで発生しない場合）。

次に、の個別のサブセットの数をカウントします s 次のことを行うことができます（Scala、Python、Pseudo-Codeのろくでなしの混合物で）：

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))))

私の意見では、パフォーマンスの理由から、この種の純粋に機能的な解決策を放棄する方が良いでしょう...リストや木でうまく機能しますが、それを超えて難しくなります。