Scala 中 ListBuffer[Set[Int]] 中的依赖项

Question

我正在解决一个问题，我得到了这个：

ant : scala.collection.mutable.ListBuffer[Set[Int]] = ListBuffer(Set(), Set(0), Set(0), Set(1), Set(2), Set(1), Set(3,4), Set(5, 6), Set(7))

ListBuffer中的Set表示依赖关系，例如：ant(1)是Set(0)，也就是说ant(1)依赖于ant(0)，即Set()。和其他的一样，另一个例子：ant(7) 是 Set(5, 6) 这意味着 ant(7) 依赖于 ant(5) 和 ant(6).

我需要获取的是一个新的ListBuffer[Set[Int]]，其中所有Set之间的依赖没有重复，例如：ant(6) depends of ant(3) and ant(4)，在同时 ant(3) 依赖于 ant(1) 并且 ant(4) 依赖于 ant(2)，而 ant(1) 和 ant(2) 依赖于 ant(0)，所以所有依赖项的结果在ant(6) 是：Set(3,4,1,2,0)

所以初始ListBuffer的结果应该是：

 solution : scala.collection.mutable.ListBuffer[Set[Int]] = ListBuffer(Set(), Set(0), Set(0), Set(1,0), Set(2,0), Set(1,0), Set(3,4,1,2,0), Set(5,6,1,3,4,0,2), Set(7,5,6,1,0,4,3,2))

哪种方法最好？

谢谢。

Answer 1

对于您要表示的内容，这绝对是错误的数据结构。要获得您想要的结果，您将不得不经历一系列比数据结构本身更复杂的步骤。

所以我们从这里开始。

import collection.mutable.ListBuffer
val ant: ListBuffer[Set[Int]] = ListBuffer(Set(), Set(0), Set(0), Set(1), Set(2),
                                           Set(1), Set(3,4), Set(5, 6), Set(7))

现在我们需要将 sub-dependencies 添加到每个当前的依赖集。由于这些是 Int 中的 Set，因此显示顺序无关紧要。

ant.map(_.flatMap(x => ant(x) + x))
// ListBuffer(Set(), Set(0), Set(0), Set(0, 1), Set(0, 2), Set(0, 1), Set(1, 3, 2, 4), Set(5, 1, 6, 3, 4), Set(5, 6, 7))

现在我们需要重复这个过程，直到新的结果与之前的结果相同。 Stream 迭代器将设置重复，我们将 dropWhile 每个元素都与前一个不同。

// a ListBuffer Stream
val lbStrm: Stream[ListBuffer[Set[Int]]] = 
     Stream.iterate[ListBuffer[Set[Int]]](ant)(_.map(_.flatMap(x => ant(x) + x)))

// grab the first one after the results settle
lbStrm.zipWithIndex.dropWhile{case (lb,x) => lb != lbStrm(x+1)}.head._1
// ListBuffer(Set(), Set(0), Set(0), Set(0, 1), Set(0, 2), Set(0, 1), Set(0, 1, 2, 3, 4), Set(0, 5, 1, 6, 2, 3, 4), Set(0, 5, 1, 6, 2, 7, 3, 4))

不漂亮，但可行。重新设计那个起始数据结构会好得多。

Scala 中 ListBuffer[Set[Int]] 中的依赖项

Dependencies in a ListBuffer[Set[Int]] in Scala

scala

set

listbuffer