def perms3[T](L: List[T]):List[List[T]] = L match { //permutations of a single element is simply a list containing a list with that element case head :: Nil => List(List(head)) case head :: tail => { (List[List[T]]() /: L)((result, head) => (List[List[T]]() /: perms3(L-head))((accum, tailperm) => (head :: tailperm) :: accum) ::: result) } case Nil => List[List[T]]() }

I actually wound up with three versions (perms, perms2, perms3, all shown below) while trying to get rid of the mutable variable from the first version:

object Perm { def main(args : Array[String]) : Unit = { tryPerms ("A" :: Nil) tryPerms ("A" :: "B" :: Nil) tryPerms ("A" :: "B" :: "C" :: Nil) } def tryPerms(input: List[String]) { println ("Permutations of " + input.mkString(",") + ", v1") for (perm <- perms (input)) println (perm.mkString(",")) println ("Permutations of " + input.mkString(",") + ", v2") for (perm <- perms2 (input)) println (perm.mkString(",")) println ("Permutations of " + input.mkString(",") + ", v3") for (perm <- perms3 (input)) println (perm.mkString(",")) println } def perms[T](L: List[T]):List[List[T]] = L match { //permutations of a single element is simply a list containing a list with that element case head :: Nil => List(List(head)) case head :: tail => { var result = List[List[T]]() for (head <- L; tail <- perms(L-head)) result = (head :: tail) :: result result } case Nil => List[List[T]]() } def perms2[T](L: List[T]):List[List[T]] = L match { //permutations of a single element is simply a list containing a list with that element case head :: Nil => List(List(head)) case head :: tail => { L.foldLeft(List[List[T]]())((result, current) => { perms2(L-current).foldLeft(List[List[T]]())((r, c) => { (current :: c) :: r }) ::: result }) } case Nil => List[List[T]]() } def perms3[T](L: List[T]):List[List[T]] = L match { //permutations of a single element is simply a list containing a list with that element case head :: Nil => List(List(head)) case head :: tail => { (List[List[T]]() /: L)((result, head) => (List[List[T]]() /: perms3(L-head))((accum, tailperm) => (head :: tailperm) :: accum) ::: result) } case Nil => List[List[T]]() } }

Version two gets rid of the offensive mutable result variable from version one. Version three re-expresses version two more concisely (perhaps to the point of mild illegibility!).

Output is:

Permutations of A, v1 A Permutations of A, v2 A Permutations of A, v3 A Permutations of A,B, v1 B,A A,B Permutations of A,B, v2 B,A A,B Permutations of A,B, v3 B,A A,B Permutations of A,B,C, v1 C,A,B C,B,A B,A,C B,C,A A,B,C A,C,B Permutations of A,B,C, v2 C,A,B C,B,A B,A,C B,C,A A,B,C A,C,B Permutations of A,B,C, v3 C,A,B C,B,A B,A,C B,C,A A,B,C A,C,B

## 3 comments:

This is better:

def perms[T](l : List[T]) : List[List[T]] =

if (l.isEmpty) List(l) else

for (h <- l; t <- perms(l - h)) yield h :: t

Very cool! TY.

All of these methods including Jesper's are recursive. This severely limits the size of the lists you want to permute otherwise you will get heap space issues. An iterative method would probably be a better idea.

## Post a Comment