41 lines
676 B
Scala
41 lines
676 B
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))
|