36 lines
1.2 KiB
Plaintext
36 lines
1.2 KiB
Plaintext
# All of this is built-in
|
|
Derangements([1 .. 4]);
|
|
# [ [ 2, 1, 4, 3 ], [ 2, 3, 4, 1 ], [ 2, 4, 1, 3 ], [ 3, 1, 4, 2 ], [ 3, 4, 1, 2 ], [ 3, 4, 2, 1 ],
|
|
# [ 4, 1, 2, 3 ], [ 4, 3, 1, 2 ], [ 4, 3, 2, 1 ] ]
|
|
Size(last);
|
|
# 9
|
|
|
|
NrDerangements([1 .. 4]);
|
|
# 9
|
|
|
|
# An implementation using formula D(n + 1) = n*(D(n) + D(n - 1))
|
|
NrDerangementsAlt_memo := [1, 0];
|
|
NrDerangementsAlt := function(n)
|
|
if not IsBound(NrDerangementsAlt_memo[n + 1]) then
|
|
NrDerangementsAlt_memo[n + 1] := (n - 1)*(NrDerangementsAlt(n - 1) + NrDerangementsAlt(n - 2));
|
|
fi;
|
|
return NrDerangementsAlt_memo[n + 1];
|
|
end;
|
|
|
|
L := List([0 .. 9]);
|
|
|
|
PrintArray(TransposedMat([L,
|
|
List(L, n -> Size(Derangements([1 .. n]))),
|
|
List(L, n -> NrDerangements([1 .. n])),
|
|
List(L, NrDerangementsAlt)]));
|
|
# [ [ 0, 1, 1, 1 ],
|
|
# [ 1, 0, 0, 0 ],
|
|
# [ 2, 1, 1, 1 ],
|
|
# [ 3, 2, 2, 2 ],
|
|
# [ 4, 9, 9, 9 ],
|
|
# [ 5, 44, 44, 44 ],
|
|
# [ 6, 265, 265, 265 ],
|
|
# [ 7, 1854, 1854, 1854 ],
|
|
# [ 8, 14833, 14833, 14833 ],
|
|
# [ 9, 133496, 133496, 133496 ] ]
|