15 lines
544 B
Scala
15 lines
544 B
Scala
def derangements(n: Int) =
|
|
(1 to n).permutations.filter(_.zipWithIndex.forall{case (a, b) => a - b != 1})
|
|
|
|
def subfactorial(n: Long): Long = n match {
|
|
case 0 => 1
|
|
case 1 => 0
|
|
case _ => (n - 1) * (subfactorial(n - 1) + subfactorial(n - 2))
|
|
}
|
|
|
|
println(s"Derangements for n = 4")
|
|
println(derangements(4) mkString "\n")
|
|
|
|
println("\n%2s%10s%10s".format("n", "derange", "subfact"))
|
|
(0 to 9).foreach(n => println("%2d%10d%10d".format(n, derangements(n).size, subfactorial(n))))
|
|
(10 to 20).foreach(n => println(f"$n%2d${subfactorial(n)}%20d"))
|