# Find All Permutations of String in Scala

I created the following function, permutations, to produce all permutations of a List[A].

Example:

scala> net.Permutations.permutations("ab".split("").toList)
res3: List[List[String]] = List(List(a, b), List(b, a))


Code:

object Permutations {

def permutations[A](str: List[A]): List[List[A]] =
str match {
case Nil => List(Nil)
case list @ _ :: _ =>
val shifteds: List[List[A]] =
shiftN(list, list.length)

shifteds.flatMap {
permutations(tail).map { lists: List[A] =>
}
case Nil => Nil
}
}

private def shiftN[A](list: List[A], n: Int): List[List[A]] = {
if (n <= 0) Nil
else {
val shifted: List[A] = shift(list)
shifted :: shiftN(shifted, n - 1)
}
}

private def shift[A](arr: List[A]): List[A] = arr match {
case Nil => Nil
}
}


I think it's correct since the following property-based check succeeds:

import munit.ScalaCheckSuite
import org.scalacheck.Prop._
import org.scalacheck.Gen

class PermutationsSpec extends ScalaCheckSuite {

private val listGen: Gen[List[Int]] =
for {
n <- Gen.choose(0, 7)
list <- Gen.listOfN(n, Gen.posNum[Int])
} yield list

property("permutations works") {
forAll(listGen) { list: List[Int] =>
val mine: List[List[Int]] = Permutations.permutations(list)
val stdLib: List[List[Int]] = list.permutations.toList
assert(stdLib.diff(mine).isEmpty)
}
}

}


Please evaluate for correctness, concision and performance.

• Your definition of permutation differs from that of the Scala standard library: permutations(List(1,2,2)).length vs List(1,2,2).permutations.length. Is that intentional? – jwvh Feb 24 at 4:39

The code looks to be correct, yes, the testing looks good too. I was thinking whether List(List()) for the input List() makes sense, but it seems like that's a sensible output.

For the code readability I'd rename str, especially since it's not really a string, but a list. The complicated match expression in permutations can just be simplified to case _ and in the body the original argument can be reused again.

I'd also inline shifteds value since it's just a single call and the name doesn't really tell me anything. On that note, docstrings for the functions might be a nice touch, especially for the shift and shiftN methods.

The unused case labels can also just be _ everywhere. Depends of course, for me this makes it clearer that really there's always just two cases, either matching an empty list, or a non-empty one, there's no third case.

Would look like this then:

object Permutations {
def permutations[A](list: List[A]): List[List[A]] =
list match {
case Nil => List(Nil)
case _ =>
shiftN(list, list.length).flatMap {
case _ => Nil
}
}

def shiftN[A](list: List[A], n: Int): List[List[A]] = {
if (n <= 0) Nil
else {
val shifted: List[A] = shift(list)
shifted :: shiftN(shifted, n - 1)
}
}

def shift[A](list: List[A]): List[A] = list match {
case _ => Nil
}
}


Lastly, performance-wise it depends what your constraints are: For List input and List output, restricting it to single linked lists, this is fine, though I haven't benchmarked them of course. Potentially converting the shifted :: shiftN(...) call into using an accumulator might be worth a bit, instead of having a deep call stack, but again, it'll probably only matter for longer inputs.

But there are way quicker algorithms, though you might want to copy the input into a vector that can be accessed in constant time for each index. (I found the QuickPerm algorithm, as explained here absolutely straightforward to implement from scratch.)

Here is a another solution using fold that has the similar performance characteristics. One difference is that it doesn't have to compute the linear List Length


def inserts[A](x: A): List[A] => List[List[A]] =
ls =>
ls match {
case Nil       => List(List(x))
case (y :: ys) => (x :: y :: ys) :: (inserts(x)(ys)).map( y :: _)
}
def permutations[A](ls: List[A]): List[List[A]] =
ls.foldRight(List(List[A]()))((x, xss) => xss.flatMap(inserts(x)))


• Welcome to CodeReview@SE. I see an independent solution proposed. doesn't have to compute [list length] is a bit thin on insight about the code presented for review - CR is not about insight about the problem the code presented is to solve. – greybeard Feb 24 at 9:16