44 lines
1.2 KiB
Text
44 lines
1.2 KiB
Text
function deranged(sequence s1, sequence s2)
|
|
for i=1 to length(s1) do
|
|
if s1[i]==s2[i] then return 0 end if
|
|
end for
|
|
return 1
|
|
end function
|
|
|
|
function derangements(integer n)
|
|
sequence ts = tagset(n)
|
|
sequence res = {}
|
|
for i=1 to factorial(n) do
|
|
sequence s = permute(i,ts)
|
|
if deranged(s,ts) then
|
|
res = append(res,s)
|
|
end if
|
|
end for
|
|
return res
|
|
end function
|
|
|
|
function subfactorial(integer n)
|
|
if n<2 then return 1-n end if
|
|
return (n-1)*(subfactorial(n-1)+subfactorial(n-2))
|
|
end function
|
|
|
|
?derangements(4)
|
|
for n=0 to 9 do
|
|
printf(1,"%d: counted:%d, calculated:%d\n",{n,length(derangements(n)),subfactorial(n)})
|
|
end for
|
|
string msg = iff(machine_bits()=32?" (incorrect on 32-bit!)":"") -- (fine on 64-bit)
|
|
printf(1,"!20=%d%s\n",{subfactorial(20),msg})
|
|
|
|
include mpfr.e
|
|
function mpz_sub_factorial(integer n)
|
|
-- probably not the most efficient way to do this!
|
|
if n<2 then return sprintf("%d",{1-n}) end if
|
|
mpz f = mpz_init(mpz_sub_factorial(n-1)),
|
|
g = mpz_init(mpz_sub_factorial(n-2))
|
|
mpz_add(f,f,g)
|
|
mpz_mul_si(f,f,n-1)
|
|
string res = mpz_get_str(f)
|
|
{f,g} = mpz_free({f,g})
|
|
return res
|
|
end function
|
|
printf(1,"!20=%s (mpfr)\n",{mpz_sub_factorial(20)})
|