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 a :: b :: Nil => List(List(a, b), List(b, a))
case list @ _ :: _ =>
val shifteds: List[List[A]] =
shiftN(list, list.length)
shifteds.flatMap {
case head :: tail =>
permutations(tail).map { lists: List[A] =>
head :: lists
}
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 head :: tail => tail ++ List(head)
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.