How to avoid java.lang.OutOfMemoryError Exception when calculating all possible combinations in Scala?

Question

I know that there are a lot of related questions regarding java.lang.OutOfMemoryError: GC overhead limit exceeded (for example How to avoid java.lang.OutOfMemoryError?) and I know that my issue is caused by my bad implementation but I don't know how to fix it.

So, my goal is to get all possible combinations with repetitions from a List. I achieved this task by using the code proposed in the answer by Mark Lister of this question. It works perfectly, but apparently getting all combinations within a range of 10 by using a List with 52 Elements is too much for my computer. Any ideas how I can fix this?

Probably better than just gathering huge Lists of combinations, I could just process each word when producing the combo?

Here is my code:

object MyApp extends App {

  val letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".toList

  run(10)

  def mycomb[T](n: Int, l: List[T]): List[List[T]] =
    n match {
      case 0 => List(List())
      case _ => for (el <- l;
                     sl <- mycomb(n - 1, l dropWhile {
                       _ != el
                     }))
        yield el :: sl
    }

  def comb[T](n: Int, l: List[T]): List[List[T]] = mycomb(n, l.distinct)

  def run(n: Int): Unit = {

    for (i <- 1 to n) {
      val combo = comb(i, letters)

      combo.par.foreach { word =>
        println(word.mkString(""))
        // Process each word one by one in parallel
      }
    }
  }

}

You are better off a) using a strategy which doesn't produce duplicates, b) output each result as you get them. This way you won't run out of memory. — Peter Lawrey
– Peter Lawrey, Commented Apr 6, 2016 at 16:18
@PeterLawrey Exactly, that's what I thought! I did it this way, because I thought initially that I could use a concurrent approach with .par. — John Doe
– John Doe, Commented Apr 6, 2016 at 16:22
Use Stream or Iterator instead of List [def combinations(n: Int): Iterator[Seq[A]]](scala-lang.org/api/current/#scala.collection.Seq) — Andrzej Jozwik
– Andrzej Jozwik, Commented Apr 6, 2016 at 16:43
@AndrzejJozwik Thank you for your comment. Unfortunately, I am a Scala beginner. Could you please provide a code example? — John Doe
– John Doe, Commented Apr 6, 2016 at 16:54

Andrzej Jozwik · Accepted Answer · 2016-04-21 08:52:41Z

I found some time and my solution for all possible combinations without repetitions:

  val digits = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

  def concat[T](it1: Iterator[T], it2: => Iterator[T]): Iterator[T] = new Iterator[T] {
    def hasNext: Boolean = it1.hasNext || it2.hasNext

    def next(): T = if (it1.hasNext) {
      it1.next()
    } else {
      it2.next()
    }
  }

  def combinationWithoutRepetitions[T](k: Int, seq: Seq[T]): Iterator[Seq[T]] = {
    def combination(k: Int, acc: Seq[T], tail: Seq[T]): Iterator[Seq[T]] = k match {
      case 0 =>
        Iterator.empty
      case 1 =>
        tail.iterator.map { t => t +: acc }
      case _ if tail.nonEmpty =>
        val it1 = combination(k - 1, tail.head +: acc, tail.tail)
        lazy val it2 = combination(k, Seq.empty, tail.tail)
        concat(it1, it2)
      case _ =>
        Iterator.empty
    }

    combination(k, Seq.empty, seq)
  }

  //TEST
  val iterator = combinationWithoutRepetitions(10, digits.toSeq) // it should return immediatelly
  println(s"${iterator.next()}")
  println(s"${iterator.next()}")

  combinationWithoutRepetitions(2, digits.toSeq).foreach{
         el => println(s"$el")
  }

I used lazy loading. Function concat create iterator from two iterators - first iterate by first, and when this iterator will be empty - starts iterate by second.

Update

Combinations with repetitions (based on previous function):

  def combinationWithRepetitions[T](k: Int, sequence: Seq[T]): Iterator[Seq[T]] = new Iterator[Seq[T]] {
    val without = combinationWithoutRepetitions(k, sequence)
    var combination: Iterator[Seq[T]] = Iterator.empty

    def hasNext: Boolean = {
      combination.hasNext || without.hasNext
    }

    def next(): Seq[T] = {
      if (combination.isEmpty) {
        combination = without.next().permutations
      }
      combination.next()
    }
  }

Collectives™ on Stack Overflow

How to avoid java.lang.OutOfMemoryError Exception when calculating all possible combinations in Scala?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related