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

yes, but you have a good answer below (eastsun) that works with a different order — Giovanni Caporaletti, Sep 14 '14 at 09:20

Eastsun · Answer 1 · 2014-09-14T08:34:45.457

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)

nice one, +1. Only a minor stylistic remark: `1 to limit iterator` is hard to read, and it raises a postfix-operator warning. I would argue that `(1 to limit).iterator` is clearer. — Gabriele Petronella, Sep 13 '14 at 14:12
The order is different than what you'd have using the for comprehension as in my example. e.g. for 3,4 it should be: 1 1 1 - 1 1 2 - 1 1 3 - 1 2 2 - 1 2 3, etc — Giovanni Caporaletti, Sep 13 '14 at 14:15

dk14 · Accepted Answer · 2015-04-03T18:20:30.117

3

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

edited Apr 03 '15 at 18:20

answered Sep 13 '14 at 13:51

dk14

22,206
4
51
88

something's wrong, intsListIterator(5,5) produces Lists of 4 elements – Giovanni Caporaletti Sep 13 '14 at 14:45
I also translated this to for comprehension but yours looks more compact – Giovanni Caporaletti Sep 13 '14 at 15:15
1

added for-comprehension – dk14 Sep 13 '14 at 15:29

Jatin · Answer 3 · 2014-09-14T16:59:59.957

2

Well this works:

def intsIterator(n: Int, limit: Int) = (1 to n).map(List.fill(limit)(_)).flatten.combinations(limit).filter(l => (l, l.tail).zipped.forall(_ <= _))

scala> intsIterator(5,3) mkString "\n"
res16: String =
Vector(1, 2, 3)
Vector(1, 2, 4)
Vector(1, 2, 5)
Vector(1, 3, 4)
Vector(1, 3, 5)
Vector(1, 4, 5)
Vector(2, 3, 4)
Vector(2, 3, 5)
Vector(2, 4, 5)
Vector(3, 4, 5)

Basically you get a combination i.e. n C limit and then you filter based on if a list is sorted or not.

Or a more readable version:

def intsIterator(n: Int, limit: Int) = (1 to n).map(List.fill(limit)(_)).flatten.combinations(limit).filter(l => l.sorted == l)

edited Sep 14 '14 at 16:59

answered Sep 13 '14 at 13:49

Jatin

31,116
15
98
163

this doesn't work. Try this: intsIterator(10, 10000).take(100) foreach println – Giovanni Caporaletti Sep 13 '14 at 13:59
I like this, as it wont stack overflow, its a little inefficient though since it has to filter in quite an exhaustive way – samthebest Sep 14 '14 at 06:19
@TrustNoOne It does now. I had a wrong assumption that there can be no duplicates. Now it works as you expected it to. – Jatin Sep 14 '14 at 17:00

samthebest · Answer 4 · 2014-09-14T09:50:52.407

If efficiency or scalability where important I would act on Vectors, I wouldn't use recursion and create an Iterator instead of a List

new Iterator() {
  val max = limit - 1 // makes logic simpler
  var cur = Vector.fill(n - 1)(1) :+ 0
  var (i, v) = (n - 1, 1)

  def hasNext(): Boolean = cur.head != max

  def next(): List[Int] = {
    if (v <= max) 
      cur = cur.updated(i, v)
    else {
      i -= 1
      if (cur(i) == max - 1) 
        cur = cur.update(i, max)
      else {
        v = cur(i) + 1
        cur = cur.take(i) ++ Vector.fill(n - i)(v)
        i = n - 1
      }
    }
    v += 1
    cur.toList // you could leave as a Vector
  }
}

Of course you could always turn this into a List with toList

(Not tested; wrote with phone)

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

4 Answers4