Зависимости в ListBuffer [Set [Int]] в Scala

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 представляет собой зависимость, например: муравей (1) является Set (0), что означает, что ant (1) зависит от ant (0), который является Set(). То же самое с другими, еще один пример: ant (7) - это Set (5, 6), что означает, что ant (7) зависит от ant (5) и ant (6).

Что мне нужно получить, это новый ListBuffer [Set [Int]] со всеми зависимостями между наборами без повторений, например: ant (6) зависит от ant (3) и ant (4), на в то же время ант (3) зависит от муравьиных (1) и ант (4) зависит от муравьиных (2), а ant (1) и ant (2) зависит от ant (0), поэтому результат со всеми зависимостями в муравьином (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)) 

Теперь нам нужно добавить субзависимости к каждому из текущих наборов зависимостей. Так как это Set s от Int s, порядок представления не имеет значения.

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

Теперь нам нужно повторить это, пока новый результат не будет таким же, как и предыдущий результат. A 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)) 

Не очень, но выполнимо. Было бы намного лучше перепроектировать эту начальную структуру данных.