0

我有一个简单的任务来找到最常发生的组合，当我们丢弃 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))
}

提前致谢

4

1 回答 1

0

我认为您可以使用 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 +: _) }
  }
}

或者通过将递归调用替换为 fold 更简洁：

  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，因此流甚至列表都是可行的方法；上面的代码仍然有效，因为迭代器上的 toSeq 实际上返回了一个惰性流）。

如果您正在考虑骰子总和而不是组合的统计信息，则可以更新 dropLowest 函数： def dropLowest(l: Seq[Int]) = l.sum - l.min

于 2013-10-15T14:22:10.747 回答