Find the missing permutation: Difference between revisions

=={{header|Scala}}==

{{works with|Scala|2.8}}

<lang scala>def fat(n: Int) = (2 to n).foldLeft(1)(_*_)

def perm[A](x: Int, a: Seq[A]): Seq[A] = if (x == 0) a else {

val n = a.size

val fatN1 = fat(n - 1)

val fatN = fatN1 * n

val p = x / fatN1 % fatN

val (before, Seq(el, after @ _*)) = a splitAt p

el +: perm(x % fatN1, before ++ after)

}

def findMissingPerm(start: String, perms: Array[String]): String = {

for {

i <- 0 until fat(start.size)

p = perm(i, start).mkString

} if (!perms.contains(p)) return p

""

}

val perms = """ABCD

CABD

ACDB

DACB

BCDA

ACBD

ADCB

CDAB

DABC

BCAD

CADB

CDBA

CBAD

ABDC

ADBC

BDCA

DCBA

BACD

BADC

BDAC

CBDA

DBCA

DCAB""".stripMargin.split("\n")

println(findMissingPerm(perms(0), perms))</lang>