[SCALA] 스칼라 여러 Seqs의 게으른 직교 제품

스칼라 여러 Seqs의 게으른 직교 제품

이 같은 여러 Seqs에 직교 제품을 생성하는 간단한 방법을 구현 :

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

그것은 한 번에 전체 제품을 계산으로 분명히,이 사람은 정말 느립니다. 사람이 스칼라에서이 문제에 대한 게으른 솔루션을 구현 했습니까?

UPD

OK, 그래서 데카르트 제품의 반복자의 reeeeally 바보,하지만 작업 버전을 구현했습니다. 미래 매니아 여기를 게시 :

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

해결법

1. ==============================

   1.여기에 주어진 문제에 대한 내 솔루션입니다. 게으름이 단순히 이해에 사용의 "루트 수집"에 .view를 사용하여 발생합니다.

   여기에 주어진 문제에 대한 내 솔루션입니다. 게으름이 단순히 이해에 사용의 "루트 수집"에 .view를 사용하여 발생합니다.

   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)
   

   이것을 얻기 위해, I 그것을 함수 (a, b) => (A, B)를 통과하는 결합 https://stackoverflow.com/a/4515071/53974 정의 기능에서 시작. 그 코드는 유형의 기능 (A, A)를 기대하기 때문에, 즉 아주, 직접 작동하지 않았다 => A. 난 그냥 코드를 조금 적응 그래서.

2. ==============================

   2.이들은 출발점이 될 수 있습니다

   이들은 출발점이 될 수 있습니다

3. ==============================

   3.

   def cartesian[A](list: List[List[A]]): List[List[A]] = {
     list match {
       case Nil => List(List())
       case h :: t => h.flatMap(i => cartesian(t).map(i :: _))
     }
   }
   

4. ==============================

   4.이건 어떤가요:

   이건 어떤가요:

     def cartesian[A](list: List[Seq[A]]): Iterator[Seq[A]] = {
       if (list.isEmpty) {
         Iterator(Seq())
       } else {
         list.head.iterator.flatMap { i => cartesian(list.tail).map(i +: _) }
       }
     }
   

   간단하고 게으른)

5. ==============================

   5.모든 요소를 ​​생성하지 않고, 가능한 모든 값의 인덱스에 숫자를 변환하는 방법을 https://stackoverflow.com/a/8318364/312172 : 당신은 여기에서 찾아보실 수 있습니다.

   모든 요소를 ​​생성하지 않고, 가능한 모든 값의 인덱스에 숫자를 변환하는 방법을 https://stackoverflow.com/a/8318364/312172 : 당신은 여기에서 찾아보실 수 있습니다.

   이 기술은 스트림을 구현하는 데 사용할 수 있습니다.

from https://stackoverflow.com/questions/8321906/lazy-cartesian-product-of-several-seqs-in-scala by cc-by-sa and MIT license