create a scala function that generates ordered list of integers of length N

Question

Suppose I have a simple function that builds an iterator of all the lists of two positive integers (x,y) that are <1000 and have x <= y

def twoIntsIterator(): Iterator[List[Int]] = {
  for {
    x <- Iterator.range(1, 1000)
    y <- Iterator.range(x, 1000)
  } yield List(x, y)
}

How would you implement a function intsListIterator(n: Int, limit: Int) that geneneralizes the list creation to lists of variable length? Such a function would produce the same output of the one above for n=2 and limit=1000. If called with n=3 and limit=4 it would return an iterator that produces the following:

List(1,1,1)
List(1,1,2)
List(1,1,3)
List(1,2,2)
List(1,2,3)
List(1,3,3)
List(2,2,2)
List(2,2,3)
List(2,3,3)
List(3,3,3)

N.B.: I used iterators but they could have been views, the point is the variable list length

Answer 1

Here is my solution:

scala> def gen(n: Int, limit: Int): Iterator[List[Int]] = n match {
     |   case 0 => Iterator(Nil)
     |   case _ => for(t <- 1 to limit iterator;s <- gen(n-1, t)) yield s:+t
     | }

EDIT The following method generating all Lists with size n and its elements satisfy start <= x < end, you can def intsListIterator by

def intsListIterator(n: Int, limit: Int) = gen(n, 1, limit)

scala> def gen(n: Int, start: Int, end: Int): Iterator[List[Int]] = n match {
     |   case 0 => Iterator(Nil)
     |   case _ => for(i <- Iterator.range(start, end);s <- gen(n-1,i,end)) yield i::s
     | }
gen: (n: Int, start: Int, end: Int)Iterator[List[Int]]

scala> gen(3, 1, 4) foreach println
List(1, 1, 1)
List(1, 1, 2)
List(1, 1, 3)
List(1, 2, 2)
List(1, 2, 3)
List(1, 3, 3)
List(2, 2, 2)
List(2, 2, 3)
List(2, 3, 3)
List(3, 3, 3)

scala> gen(7, -3, 4) take 10 foreach println
List(-3, -3, -3, -3, -3, -3, -3)
List(-3, -3, -3, -3, -3, -3, -2)
List(-3, -3, -3, -3, -3, -3, -1)
List(-3, -3, -3, -3, -3, -3, 0)
List(-3, -3, -3, -3, -3, -3, 1)
List(-3, -3, -3, -3, -3, -3, 2)
List(-3, -3, -3, -3, -3, -3, 3)
List(-3, -3, -3, -3, -3, -2, -2)
List(-3, -3, -3, -3, -3, -2, -1)
List(-3, -3, -3, -3, -3, -2, 0)

Answer 2

Just use recursion:

def produce(n: Int, limit: Int, k: Int = 1): Iterator[List[Int]] = {
  Iterator.range(k, limit) flatMap {
    case x if n > 1 => produce(n - 1, limit, x).map(x :: _)
    case x => Iterator(List(x))
  }
}

Or with for-comprehension:

def produce(n: Int, limit: Int, k: Int = 1): Iterator[List[Int]] = for {
   x <- k to limit - 1 iterator;
   y <- if (n > 1) produce(n - 1, limit, x) else Iterator(Nil)
} yield x :: y