Декартовой поток продукта scala

Question

У меня была простая задача найти комбинацию, которая встречается чаще всего, когда мы бросаем 4 кубических кубика, удаляем одну с наименьшими точками.

Итак, вопрос: существуют ли классы Scala для генерации потоков декартовых продуктов в Scala? Когда нет - как реализовать его самым простым и эффективным способом?

Вот код и сравнение с наивной реализации в Scala:

object D extends App { 
    def dropLowest(a: List[Int]) = { 
    a diff List(a.min) 
    } 

    def cartesian(to: Int, times: Int): Stream[List[Int]] = { 
    def stream(x: List[Int]): Stream[List[Int]] = { 
     if (hasNext(x)) x #:: stream(next(x)) else Stream(x) 
    } 

    def hasNext(x: List[Int]) = x.exists(n => n < to) 

    def next(x: List[Int]) = { 
     def add(current: List[Int]): List[Int] = { 
     if (current.head == to) 1 :: add(current.tail) else current.head + 1 :: current.tail // here is a possible bug when we get maximal value, don't reuse this method 
     } 
     add(x.reverse).reverse 
    } 

    stream(Range(0, times).map(t => 1).toList) 
    } 

    def getResult(list: Stream[List[Int]]) = { 
    list.map(t => dropLowest(t).sum).groupBy(t => t).map(t => (t._1, t._2.size)).toMap 
    } 

    val list1 = cartesian(6, 4) 

    val list = for (i <- Range(1, 7); j <- Range(1,7); k <- Range(1, 7); l <- Range(1, 7)) yield List(i, j, k, l) 
    println(getResult(list1)) 
    println(getResult(list.toStream) equals getResult(list1)) 
} 

Заранее спасибо

Answer 1

Я думаю, вы можете упростить ваш код с помощью flatMap:

val stream = (1 to 6).toStream 

def cartesian(times: Int): Stream[Seq[Int]] = { 
    if (times == 0) { 
    Stream(Seq()) 
    } else { 
    stream.flatMap { i => cartesian(times - 1).map(i +: _) } 
    } 
} 

Может быть немного более эффективным (с точки зрения памяти) будет использовать Итераторы вместо:

val pool = (1 to 6) 

def cartesian(times: Int): Iterator[Seq[Int]] = { 
    if (times == 0) { 
    Iterator(Seq()) 
    } else { 
    pool.iterator.flatMap { i => cartesian(times - 1).map(i +: _) } 
    } 
} 

или даже более кратким путем замены рекурсивных вызовов складкой:

def cartesian[A](list: Seq[Seq[A]]): Iterator[Seq[A]] = 
    list.foldLeft(Iterator(Seq[A]())) { 
     case (acc, l) => acc.flatMap(i => l.map(_ +: i)) 
    } 

, а затем:

cartesian(Seq.fill(4)(1 to 6)).map(dropLowest).toSeq.groupBy(i => i.sorted).mapValues(_.size).toSeq.sortBy(_._2).foreach(println) 

(Обратите внимание, что вы не можете использовать GroupBy на итераторы, так Streams или даже списки это путь к тому, чтобы быть таким; выше код все еще действителен, так как toSeq на Iterator фактически возвращает ленивый поток).

Если вы рассматриваете статистику по суммам кубиков вместо комбинаций, вы можете обновить dropLowest fonction: def dropLowest(l: Seq[Int]) = l.sum - l.min