CODEWITHSUNDEEP
scalaout-of-memorypermutationheap-memory
JoeDortman
JoeDortman

Reputation: 185

Using permutations causes: Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

I came across this problem when using permutations. I get an error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

That's obviously because a list can not hold that much information. How do I approach this problem? Should I split my list into more lists so I could hold my information? I'm not giving any code because there is way to much of it.

Upvotes: 0

Views: 177

Answers (1)

Andrey Tyukin
Andrey Tyukin

Reputation: 44928

Here is one implementation that enumerates permutations lazily:

def insertions[X](xs: List[X], y: X): Iterable[List[X]] = {
  val n = xs.size
  for (i <- 0 to n) yield {
    val (a, b) = xs.splitAt(i)
    a ++ (y :: b)
  }
}

def permutations[X](elems: List[X]): Stream[List[X]] = elems match {
  case Nil => Stream(Nil)
  case h :: t => permutations(t).flatMap(insertions(_, h))
}

For example,

permutations((0 to 10).toList) foreach println

will print all elements of the Stream.

EDIT

The question seemed to imply that List.permutations is implemented in some naive way that requires too much memory, but this is not so: the implementation in the standard library also produces an iterator that generates permutations one by one. So, one can just use 

myList.permutations

instead. One only has to make sure that one doesn't try to save all those elements in a list at once.

Upvotes: 1

Related Questions