import util.

go =>
   foreach(N in 0..9)
      println([N,num_derangements=num_derangements(N), subfactorial=subfactorial(N), subfactorial2=subfactorial2(N)])
   end,
   println(["!20", subfactorial(20)]),
   println(["!20 approx", subfactorial2(20)]),
   println("subfactorial0..30"=[subfactorial(N) : N in 0..30 ]),
   println("subfactorial2_0..30"=[subfactorial2(N) : N in 0..30 ]),
   println(["!200", subfactorial(200)]),
   nl,
   println("Syntax sugar:"),
   println("'!'(20)"='!'(20)),
   println("200.'!'()"=200.'!'()),
   println("'!!'(20)"='!!'(20)),
   println("'!-!!'(10)"='!-!!'(10)),
   nl.

num_derangements(N) = derangements(N).length.

derangements(N) = D =>
  D = [P : P in permutations(1..N), nofixpoint(P)].

% subfactorial: tabled recursive function
table
subfactorial(0) = 1.
subfactorial(1) = 0.
subfactorial(N) = (N-1)*(subfactorial(N-1)+subfactorial(N-2)).

% approximate version of subfactorial
subfactorial2(0) = 1.
subfactorial2(N) = floor(1.0*floor(factorial(N)/2.71828 + 1/2.0)).

% Factorial
fact(N) = F =>
   F1 = 1,
   foreach(I in 1..N)
     F1 := F1 * I
   end,
   F = F1.

% No fixpoint in L
nofixpoint(L) =>
   foreach(I in 1..L.length)
     L[I] != I
   end.

% Some syntax sugar. Note: the function must be an atom.
'!'(N) = fact(N).
'!!'(N) = subfactorial(N).

'!-!!'(N) = fact(N) - subfactorial(N).