26 lines
656 B
Scala
26 lines
656 B
Scala
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)) |