53 lines
1.3 KiB
Text
53 lines
1.3 KiB
Text
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).
|