def insertion[T](x: T, xs: List[T]): List[List[T]] = {
  return (0 to xs.length).map((i: Int) => {
    val p = xs.splitAt(i)
    p._1 ::: (x :: p._2)
  }).toList

  def buildInsertions(x: T, xs: List[T], before: List[T]): List[List[T]] = {
    xs match {
      case Nil => (before :+ x) :: Nil
      case head::tail => (before ::: (x :: xs)) :: buildInsertions(x, tail, before :+ head)
    }
  }
  buildInsertions(x, xs, Nil)
}

insertion(1, List(2,3,4))

def permutation[T](xs: List[T]): List[List[T]] = {
  xs match {
    case head::tail => permutation(tail) flatMap (perm => insertion(head, perm))
    case _ => List(xs)
  }
}


permutation(List(1,2,3))