Permutations (dynamic programming)

Perm.scala

object Perm extends App {

  def time[A](f: => A) = {
    val start = System.nanoTime
    val ret = f
    val dt = (System.nanoTime - start) / 1e6
    dt
  }

  class Permutations[T](implicit ord: Ordering[T]) {

    import scala.collection.mutable.HashMap

    def permutate(xs: List[T]): List[List[T]] = {
      maxStackDepth_ = -1
      n = xs.length
      perm(xs)
      val results = uniqueResults
      uniqueResults = List()
      results
    }

    private val cache: HashMap[List[T], List[List[T]]] = HashMap()
    private var uniqueResults: List[List[T]] = List()
    private var n: Int = -1
    private var maxStackDepth_ = -1

    def maxStackDepth(): Int = { maxStackDepth_ }
    private def updateMaxStackDepth(): Unit = { maxStackDepth_ = Math.max(currentStackDepth(), maxStackDepth_) }

    private def permTwoItems(xs: List[T], xsSorted: List[T]): List[List[T]] = {
      val (a, b) = (xs.head, xs.last)
      val result = List(List(a, b), List(b, a))

      cacheResult(xsSorted, result)

      maybeAddResult(result)

      result
    }

    private def permNItems(xs: List[T], xsSorted: List[T]): List[List[T]] = {
      val result = xs.zipWithIndex.flatMap { case (x, index) => {
        val parts = xs.splitAt(index)
        val diff = parts._1 ++ parts._2.tail
        perm(diff).map { x :: _ }
      }}

      cacheResult(xsSorted, result)

      maybeAddResult(result)

      result
    }

    private def perm(xs: List[T]): List[List[T]] = {
      updateMaxStackDepth()
      val result = if (xs.isEmpty) List()
      else if (xs.length == 1) List(xs)
      else {
        val xsSorted = xs.sorted
        if (cache contains xsSorted) cache(xsSorted)
        else if (xs.length == 2) permTwoItems(xs, xsSorted)
        else permNItems(xs, xsSorted)
      }

      maybeAddResult(result)

      result
    }

    def maybeAddResult(result: List[List[T]]): Unit =
      if (!result.isEmpty && result.head.length == n) { uniqueResults = result ++ uniqueResults }
      else ()

    def cacheResult(xsSorted: List[T], result: List[List[T]]): Unit = { cache += (xsSorted -> result) }

  }

  def currentStackDepth(): Int = Thread.currentThread().getStackTrace().length

  def test(): Unit = {
    val pobj = new Permutations[Int]

    (1 to 11).foreach { n => {
      import scala.util.Random

      val stackDepth = currentStackDepth()

      def randomList(n: Int): List[Int] = List.fill(n)(Random.nextInt)

      //val xs = (1 to n).toList
      val xs = randomList(n)

      var testPermutations: List[List[Int]] = List()

      def myPermutations: List[List[Int]] = pobj.permutate(xs)

      val t1 = time { myPermutations }
      //val t2 = time { testPermutations = xs.permutations.toList }

      //println(s"$n $t1 $t2")
      println(s"$n $t1 depth=(${pobj.maxStackDepth} - $stackDepth)=${pobj.maxStackDepth - stackDepth}")
      //println(s"$n ${myPermutations.length} ${myPermutations}")
      //println(s"${myPermutations} ${testPermutations}")

      //assert(myPermutations.length == testPermutations.length)
      //assert(myPermutations.toSet == testPermutations.toSet)
    }}
  }

  test()

}

/*
scalac Perm.scala && _JAVA_OPTIONS="${_JAVA_OPTIONS} -Xmx11g" scala Perm

1 0.1209 depth=(41 - 34)=7
2 0.252311 depth=(41 - 34)=7
3 0.9922 depth=(46 - 34)=12
4 1.910754 depth=(51 - 34)=17
5 6.952118 depth=(56 - 34)=22
6 19.746932 depth=(61 - 34)=27
7 32.640142 depth=(66 - 34)=32
8 65.484739 depth=(71 - 34)=37
9 670.92723 depth=(76 - 34)=42
10 6084.381431 depth=(81 - 34)=47
11 73648.393615 depth=(86 - 34)=52
*/