Friday, February 25, 2011

Scala Permutations 2

My second attempt at permutations in Scala (see first attempt):

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:

Jesper Nordenberg said...

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

Rod said...

Very cool! TY.

Joshua Hollander said...

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.

Interesting facts said...

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

Naviya Nair said...

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