Scala 中几个 Seq 的惰性笛卡尔积 [英] Lazy Cartesian product of several Seqs in Scala

问题描述

我实现了一个简单的方法来在几个 Seq 上生成笛卡尔积，如下所示:

I implemented a simple method to generate Cartesian product on several Seqs like this:

object RichSeq {
  implicit def toRichSeq[T](s: Seq[T]) = new RichSeq[T](s)
}

class RichSeq[T](s: Seq[T]) {

  import RichSeq._

  def cartesian(ss: Seq[Seq[T]]): Seq[Seq[T]] = {

    ss.toList match {
      case Nil        => Seq(s)
      case s2 :: Nil  => {
        for (e <- s) yield s2.map(e2 => Seq(e, e2))
      }.flatten
      case s2 :: tail => {
        for (e <- s) yield s2.cartesian(tail).map(seq => e +: seq)
      }.flatten
    }
  }
}

很明显，这个速度真的很慢，因为它一次计算了整个产品.有没有人在 Scala 中为这个问题实现了一个懒惰的解决方案?

Obviously, this one is really slow, as it calculates the whole product at once. Did anyone implement a lazy solution for this problem in Scala?

UPD

好的，所以我在笛卡尔积上实现了一个非常愚蠢但有效的迭代器版本.在这里为未来的爱好者发帖:

OK, So I implemented a reeeeally stupid, but working version of an iterator over a Cartesian product. Posting here for future enthusiasts:

object RichSeq {
  implicit def toRichSeq[T](s: Seq[T]) = new RichSeq(s) 
}

class RichSeq[T](s: Seq[T]) {

  def lazyCartesian(ss: Seq[Seq[T]]): Iterator[Seq[T]] = new Iterator[Seq[T]] {

    private[this] val seqs = s +: ss

    private[this] var indexes = Array.fill(seqs.length)(0)

    private[this] val counts = Vector(seqs.map(_.length - 1): _*)

    private[this] var current = 0

    def next(): Seq[T] = {
      val buffer = ArrayBuffer.empty[T]
      if (current != 0) {
        throw new NoSuchElementException("no more elements to traverse")
      }
      val newIndexes = ArrayBuffer.empty[Int]
      var inside = 0
      for ((index, i) <- indexes.zipWithIndex) {
        buffer.append(seqs(i)(index))
        newIndexes.append(index)
        if ((0 to i).forall(ind => newIndexes(ind) == counts(ind))) {
          inside = inside + 1
        }
      }
      current = inside
      if (current < seqs.length) {
        for (i <- (0 to current).reverse) {
          if ((0 to i).forall(ind => newIndexes(ind) == counts(ind))) {
            newIndexes(i) = 0
          } else if (newIndexes(i) < counts(i)) {
            newIndexes(i) = newIndexes(i) + 1
          }
        }
        current = 0
        indexes = newIndexes.toArray
      }
      buffer.result()
    }

    def hasNext: Boolean = current != seqs.length
  }
}

推荐答案

这是我对给定问题的解决方案.请注意，懒惰只是由于在用于理解的根集合"上使用 .view 引起的.

Here's my solution to the given problem. Note that the laziness is simply caused by using .view on the "root collection" of the used for comprehension.

scala> def combine[A](xs: Traversable[Traversable[A]]): Seq[Seq[A]] =
     |  xs.foldLeft(Seq(Seq.empty[A])){
     |    (x, y) => for (a <- x.view; b <- y) yield a :+ b }
combine: [A](xs: Traversable[Traversable[A]])Seq[Seq[A]]
scala> combine(Set(Set("a","b","c"), Set("1","2"), Set("S","T"))) foreach (println(_))
List(a, 1, S)
List(a, 1, T)
List(a, 2, S)
List(a, 2, T)
List(b, 1, S)
List(b, 1, T)
List(b, 2, S)
List(b, 2, T)
List(c, 1, S)
List(c, 1, T)
List(c, 2, S)
List(c, 2, T)

为了获得这个，我从 https://stackoverflow.com/中定义的函数 combine 开始a/4515071/53974，将函数 (a, b) => 传递给它；(a, b).但是，这并不能直接起作用，因为该代码需要 (A, A) => 类型的函数.一个.所以我只是稍微修改了一下代码.

To obtain this, I started from the function combine defined in https://stackoverflow.com/a/4515071/53974, passing it the function (a, b) => (a, b). However, that didn't quite work directly, since that code expects a function of type (A, A) => A. So I just adapted the code a bit.

这篇关于Scala 中几个 Seq 的惰性笛卡尔积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！