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

## 5 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.

Excellent pieces. Keep posting such kind of information on your blog. I really impressed by your blog.

html5 video player| html5 player

I have read your blog its very attractive and impressive. I like it your blog.

Java Online Training Java EE Online Training Java EE Online Training Java 8 online training Core Java 8 online training

Java Online Training from India Java Online Training from India Core Java Training Online Core Java Training Online Java Training InstitutesJava Training Institutes

## Post a Comment