Geek Answers Handbook

Create a scala function that generates an ordered list of integers of length N

Suppose I have a simple function that builds an iterator of all 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 generalizes list creation to variable-length lists? Such a function will produce the same output as above for n = 2 and limit = 1000. If called with n = 3 and limit = 4, it returns 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)

NB: I used iterators, but they could be views, dot is the length of the variable list

+4
source share
4 answers

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 understanding:

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
+3

:

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

, List n, start <= x < end, def intsListIterator

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)
+4

:

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 limitand then filter based on list sorting 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)
+2
source

If efficiency or scalability are important there, I would act on Vectors, I would not use recursion and create IteratorinsteadList

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 can always turn this into ListusingtoList

(Not verified, written from the phone)

0
source

More articles:


All Articles