如何生成元组集的传递闭包？

Question

生成一组元组的传递闭包的最佳方法是什么？

例:

• 输入 Set((1, 2), (2, 3), (3, 4), (5, 0))
• 产量 Set((1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (5, 0))

Answer 1

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

这不是一个非常有效的实现,但它很简单.