Generalised lazy permutations in Scala

Question

I want to create a generic permutations function.

def permutation(size: Int): Stream[List[Int]] = ...

permutation(1)   # same as: for { x <- (1 to 10).toStream } yield List(x)
permutation(2)   # same as: for { x <- (1 to 10).toStream;
                                  y <- (1 to 10).toStream; } yield List(x,y)

Can I get dynamically nested for-comprehensions behavior on the fly for arbitrary depth.

Answer 1

I think this gives a generalised version of what you are asking for:

def permutation[X](iter: Iterable[X], len: Int) = {
  def acc(items: List[X], count: Int): Stream[List[X]] = {
    if (count == 0) Stream(items) else iter.toStream.flatMap( x => acc(x :: items, count - 1))
  }

  acc(List.empty[X], len)
}

Example usages:

scala> permutaion(1 to 3, 3)
res4: Stream[List[Int]] = Stream(List(1, 1, 1), ?)

scala> permutaion(1 to 3, 3).toList
res5: List[List[Int]] = List(List(1, 1, 1), ?)
res5: List[List[Int]] = List(List(1, 1, 1), List(2, 1, 1), List(3, 1, 1), List(1, 2, 1), List(2, 2, 1), List(3, 2, 1), List(1, 3, 1), List(2, 3, 1), List(3, 3, 1), List(1, 1, 2), List(2, 1, 2), List(3, 1, 2), List(1, 2, 2), List(2, 2, 2), List(3, 2, 2), List(1, 3, 2), List(2, 3, 2), List(3, 3, 2), List(1, 1, 3), List(2, 1, 3), List(3, 1, 3), List(1, 2, 3), List(2, 2, 3), List(3, 2, 3), List(1, 3, 3), List(2, 3, 3), List(3, 3, 3))

scala> permutation("abc", 3)
res6: Stream[List[Char]] = Stream(List(a, a, a), ?)

scala> permutation("abc", 3).toList
res7: List[List[Char]] = List(List(a, a, a), List(b, a, a), List(c, a, a), List(a, b, a), List(b, b, a), List(c, b, a), List(a, c, a), List(b, c, a), List(c, c, a), List(a, a, b), List(b, a, b), List(c, a, b), List(a, b, b), List(b, b, b), List(c, b, b), List(a, c, b), List(b, c, b), List(c, c, b), List(a, a, c), List(b, a, c), List(c, a, c), List(a, b, c), List(b, b, c), List(c, b, c), List(a, c, c), List(b, c, c), List(c, c, c))