Puzzle Example from CCI.

Permutation.scala

object Permutation extends App {

  def generate(s: String): Array[String] = s.length() match {
    case 1 => Array(s)
    case 2 => Array("" + s(0) + s(1), "" + s(1) + s(0))
    case _ =>
      val first = s.head
      var perms = generate(s.tail)
      var result: Array[String] = Array.fill(perms.length * (perms(0).length() + 1)) { "" }
      var offset = 0

      perms foreach { p =>
        for (i <- 0 to p.length()) {
          result(offset) += p.substring(0, i)
          result(offset) += first
          result(offset) += p.substring(i, p.length())
          offset += 1 
        }
      }

      result
  }

  assert { generate("abc").corresponds(Array("abc", "bac", "bca", "acb", "cab", "cba")) { _ == _ } }
}