Lazy Evaluate all permutations of a String in Scala

permute.sc

def permsStream(s: String): Stream[String] = {
  def interleave(head: Char, tail: String) =
    0 to tail.length map (i => tail.substring(0, i) + head + tail.substring(i))

  if (s.length == 0) Stream("")
  else permsStream(s.tail) flatMap (interleave(s.head, _))
}