0

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

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]]，其中包含 Sets 之间的所有依赖关系，没有重复，例如：ant(6) 依赖于 ant(3) 和 ant(4)，同时 ant( 3) ant(1) 和 ant(4) 依赖于 ant(2)，ant(1) 和 ant(2) 依赖于 ant(0)，所以 ant(6) 中所有依赖的结果是: 设置(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))

最好的方法是什么？

谢谢。

4

1 回答 1

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

现在我们需要将子依赖添加到每个当前的依赖集中。由于这些是Sets of Ints，因此呈现顺序无关紧要。

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

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

于 2017-01-14T08:03:48.780 回答