Сглаживание Scala теряет желаемую группировку подмножеств по размеру

Question

Подсчет количества сумм кубов, равных целевому значению.

Для небольшого количества наборов этот код работает (target равно 100 против 1000). Когда целевое значение увеличивается, у системы заканчиваются ресурсы. Я не сгладил allsets с целью создания и обработки только меньших подмножеств по мере необходимости.

Как лениво создавать / использовать подмножества по размеру до тех пор, пока суммы для всех Sets одного размера не будут равны или превышать целевое значение, после чего больше ничего не нужно изучать, потому что остальные суммы будут больше чем цель.

val target = 100; val exp = 3; val maxi = math.pow(target, 1.0/exp).toInt;
target: Int = 100
exp: Int = 3
maxi: Int = 4

val allterms=(1 to maxi).map(math.pow(_,exp).toInt).to[Set];
allterms: Set[Int] = Set(1, 8, 27, 64)

val allsets = (1 to maxi).map(allterms.subsets(_).to[Vector]); allsets.mkString("\n");
allsets: scala.collection.immutable.IndexedSeq[Vector[scala.collection.immutable.Set[Int]]] = Vector(Vector(Set(1), Set(8), Set(27), Set(64)), Vector(Set(1, 8), Set(1, 27), Set(1, 64), Set(8, 27), Set(8, 64), Set(27, 64)), Vector(Set(1, 8, 27), Set(1, 8, 64), Set(1, 27, 64), Set(8, 27, 64)), Vector(Set(1, 8, 27, 64)))
res7: String =
Vector(Set(1), Set(8), Set(27), Set(64))
Vector(Set(1, 8), Set(1, 27), Set(1, 64), Set(8, 27), Set(8, 64), Set(27, 64))
Vector(Set(1, 8, 27), Set(1, 8, 64), Set(1, 27, 64), Set(8, 27, 64))
Vector(Set(1, 8, 27, 64))

allsets.flatten.map(_.sum).filter(_==target).size;
res8: Int = 1

Эта реализация теряет разделение подмножеств по размеру.

Answer 1

Вы можете добавить лень к своим вычислениям двумя способами:

1. Используйте combinations() вместо subsets(). Это создает Iterator, поэтому комбинация (набор значений Int) не будет реализована, пока она не понадобится.
2. Используйте Stream (или LazyList, если Scala 2.13.0), чтобы каждая "строка" (комбинации одинакового размера) не была реализована до тех пор, пока она не понадобится.

Затем вы можете обрезать количество строк, которые должны быть реализованы, используя тот факт, что первая комбинация каждой строки будет иметь минимум sum этой строки.

val target = 125
val exp = 2
val maxi = math.pow(target, 1.0/exp).toInt  //maxi: Int = 11

val allterms=(1 to maxi).map(math.pow(_,exp).toInt)
//allterms = Seq(1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121)

val allsets = Stream.range(1,maxi+1).map(allterms.combinations)
//allsets: Stream[Iterator[IndexedSeq[Int]]] = Stream(<iterator>, ?)
//  11 rows, 2047 combinations, all unrealized

allsets.map(_.map(_.sum).buffered)   //Stream[BufferedIterator[Int]]
       .takeWhile(_.head <= target)  // 6 rows
       .flatten                      // 1479 combinations
       .count(_ == target)
//res0: Int = 5