6

タプルのセットの推移閉包を生成するための最良の方法は何ですか？

例：

  • 入力Set((1, 2), (2, 3), (3, 4), (5, 0))
  • 出力Set((1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (5, 0))
4

4 に答える 4

7 
//one transitive step
def addTransitive[A, B](s: Set[(A, B)]) = {
  s ++ (for ((x1, y1) <- s; (x2, y2) <- s if y1 == x2) yield (x1, y2))
}

//repeat until we don't get a bigger set
def transitiveClosure[A,B](s:Set[(A,B)]):Set[(A,B)] = {
  val t = addTransitive(s)
  if (t.size == s.size) s else transitiveClosure(t)
}

println(transitiveClosure(Set((1,2), (2,3), (3,4))))

これはあまり効率的な実装ではありませんが、単純です。

于 2011-05-11T11:13:41.020 に答える
3

の助けを借りてunfold、

def unfoldRight[A, B](seed: B)(f: B => Option[(A, B)]): List[A] = f(seed) match {
  case Some((a, b)) => a :: unfoldRight(b)(f)
  case None => Nil
}

def unfoldLeft[A, B](seed: B)(f: B => Option[(B, A)]) = {
  def loop(seed: B)(ls: List[A]): List[A] = f(seed) match {
    case Some((b, a)) => loop(b)(a :: ls)
    case None => ls
  }

  loop(seed)(Nil)
}

それはかなり単純になります：

def transitiveClosure(input: Set[(Int, Int)]) = {
    val map = input.toMap
    def closure(seed: Int) = unfoldLeft(map get seed) {
        case Some(`seed`) => None
        case Some(n)      => Some(seed -> n -> (map get n))
        case _            => None
    }
    map.keySet flatMap closure
}

別の書き方closureはこれです：

def closure(seed: Int) = unfoldRight(seed) {
    case n if map.get(n) != seed => map get n map (x => seed -> x -> x)
    case _ => None
}

私自身、どちらが一番好きかわかりません。ループを回避するためのテストの優雅さが好きですSome(seed)が、同じように、の結果をマッピングする優雅さも好きですmap get n。

どちらのバージョンもseed -> seedforループを返さないため、必要に応じて追加する必要があります。ここ：

    def closure(seed: Int) = unfoldRight(map get seed) {
        case Some(`seed`) => Some(seed -> seed -> None)
        case Some(n)      => Some(seed -> n -> (map get n))
        case _            => None
    }
于 2011-05-11T21:37:05.073 に答える
2

次のように、問題を有向グラフとしてモデル化します。

タプル内の数値をグラフ内の頂点として表します。次に、各タプル（x、y）は、xからyへの有向エッジを表します。その後、Warshallのアルゴリズムを使用して、グラフの推移閉包を見つけます。

結果のグラフでは、各有向エッジが（x、y）タプルに変換されます。これは、タプルのセットの推移閉包です。

于 2011-05-11T10:26:19.247 に答える
0

あなたが持っているものがDAGであると仮定すると（あなたのサンプルデータにはサイクルがありません）、以下のコードを使用することができます。これは、DAGをTからList [T]へのマップとして想定しています。これは、を使用して入力から取得できます。

input.groupBy(_._1) mapValues ( _ map (_._2) )

推移閉包は次のとおりです。

def transitiveClosure[T]( dag: Map[ T, List[T] ] ) = {
  var tc = Map.empty[ T, List[T] ]
  def getItemTC( item:T ): List[T] = tc.get(item) match {
    case None =>
      val itemTC = dag(item) flatMap ( x => x::getItemTC(x) )
      tc += ( item -> itemTC )
      itemTC
    case Some(itemTC) => itemTC
  }
  dag.keys foreach getItemTC
  tc
}

このコードは、各要素のクロージャーを1回だけ計算します。でも：

  • このコードは、DAGを通過するパスが十分に長い場合にスタックオーバーフローを引き起こす可能性があります（再帰は末尾再帰ではありません）。
  • 大きなグラフの場合、不変のマップが必要な場合は、tcを可変のマップにして、最後に変換する方がよいでしょう。
  • 例のように要素が本当に小さい整数である場合は、マップではなく配列を使用することでパフォーマンスを大幅に向上させることができますが、そうすると複雑になることがあります。

スタックオーバーフローの問題（DAGの場合）を排除するために、トポロジカルソートを実行し、それを逆にして、アイテムを順番に処理することができます。ただし、次のページも参照してください。

グラフの最もよく知られている推移閉包アルゴリズム

于 2012-01-31T06:59:18.877 に答える