27 lines
702 B
Nim
27 lines
702 B
Nim
import algorithm, sequtils, strformat, strutils, tables
|
|
|
|
iterator derangements[T](a: openArray[T]): seq[T] =
|
|
var perm = @a
|
|
while true:
|
|
if not perm.nextPermutation():
|
|
break
|
|
block checkDerangement:
|
|
for i, val in a:
|
|
if perm[i] == val: break checkDerangement
|
|
yield perm
|
|
|
|
proc `!`(n: Natural): Natural =
|
|
if n <= 1: return 1 - n
|
|
result = (n - 1) * (!(n - 1) + !(n - 2))
|
|
|
|
echo "Derangements of 1 2 3 4:"
|
|
for d in [1, 2, 3, 4].derangements():
|
|
echo d.join(" ")
|
|
|
|
echo "\nNumber of derangements:"
|
|
echo "n counted calculated"
|
|
echo "- ------- ----------"
|
|
for n in 0..9:
|
|
echo &"{n} {toSeq(derangements(toSeq(1..n))).len:>6} {!n:>6}"
|
|
|
|
echo "\n!20 = ", !20
|