Code to enumerate permutations in Scala

Question

I coded a function to enumerate all permutations of a given list. What do you think of the code below?

def interleave(x:Int, l:List[Int]):List[List[Int]] = {
  l match { 
    case Nil => List(List(x))
    case (head::tail) =>
      (x :: head :: tail) :: interleave(x, tail).map(head :: _)
  }
}

def permutations(l:List[Int]):List[List[Int]] = {
  l match {
    case Nil => List(List())
    case (head::tail) =>
      for(p0 &lt- permutations(tail); p1 &lt- interleave(head, p0)) yield p1
  }
}

Answer 1

Given a Seq, one can already have permutations by invoking the permutations method.

scala> List(1,2,3).permutations.mkString("\n")
res3: String = 
List(1, 2, 3)
List(1, 3, 2)
List(2, 1, 3)
List(2, 3, 1)
List(3, 1, 2)
List(3, 2, 1)

Furthermore there is also a method for combinations:

scala> List(1,2,3).combinations(2).mkString("\n")
res4: String = 
List(1, 2)
List(1, 3)
List(2, 3)

Regarding your implementation I would say three things:

(1) Its good looking

(2) Provide an iterator (which is the std collections approach that allows to discard elements). Otherwise, you can get lists with 1000! elements which may not fit in memory.

scala> val longList = List((1 to 1000):_*)
longList: List[Int] = List(1, 2, 3,...


scala> permutations(longList)
java.lang.OutOfMemoryError: Java heap space
    at scala.collection.immutable.List.$colon$colon(List.scala:67)
    at .interleave(<console>:11)
    at .interleave(<console>:11)
    at .interleave(<console>:11)

(3) You should remove duplicated permutations (as observed by Luigi), since :

scala> permutations(List(1,1,3))
res4: List[List[Int]] = List(List(1, 1, 3), List(1, 1, 3), List(1, 3, 1), List(1, 3, 1), List(3, 1, 1), List(3, 1, 1))

scala> List(1,1,3).permutations.toList
res5: List[List[Int]] = List(List(1, 1, 3), List(1, 3, 1), List(3, 1, 1))

Answer 2

Consider the difference here: your version

scala> permutations(List(1,1,2)) foreach println
List(1, 1, 2)
List(1, 1, 2)
List(1, 2, 1)
List(1, 2, 1)
List(2, 1, 1)
List(2, 1, 1)

The reference version:

scala> List(1,1,2).permutations foreach println
List(1, 1, 2)
List(1, 2, 1)
List(2, 1, 1)

Answer 3

Maybe this thread is already well-saturated, but I thought I'd throw my solution into the mix:

Assuming no repeat elements:

def permList(l: List[Int]): List[List[Int]] = l match {
   case List(ele) => List(List(ele))
   case list =>
     for {
       i <- List.range(0, list.length)
       p <- permList(list.slice(0, i) ++ list.slice(i + 1, list.length))
     } yield list(i) :: p
}

With repeat elements, preventing duplicates (not as pretty):

def permList(l: List[Int]): List[List[Int]] = l match {
  case List(ele) => List(List(ele))
  case list =>
    for {
      i <- List.range(0, list.length)
      val traversedList = list.slice(0, i)
      val nextEle = list(i)
      if !(traversedList contains nextEle)
      p <- permList(traversedList ++ list.slice(i + 1, list.length))
    } yield list(i) :: p
}

It's potentially not the most "list-y", given that it uses slice and an index on the list, but it's rather concise and a slightly different way of looking at it. It works by singling out each element in the list and computing the permutations of what's remaining, and then concatenating the single element to each of those permutations. If there's a more idiomatic way to do this, I'd love to hear about it.