25 lines
789 B
Raku
25 lines
789 B
Raku
use ntheory ":all";
|
|
|
|
# Count derangements using derangement iterator
|
|
sub countderange {
|
|
my($n,$s) = (shift,0);
|
|
forderange { $s++ } $n;
|
|
$s;
|
|
}
|
|
# Count derangements using inclusion-exclusion
|
|
sub subfactorial1 {
|
|
my $n = shift;
|
|
vecsum(map{ vecprod((-1)**($n-$_),binomial($n,$_),factorial($_)) }0..$n);
|
|
}
|
|
# Count derangements using simple recursion without special functions
|
|
sub subfactorial2 {
|
|
my $n = shift;
|
|
use bigint; no warnings 'recursion';
|
|
($n < 1) ? 1 : $n * subfactorial2($n-1) + (-1)**$n;
|
|
}
|
|
|
|
print "Derangements of 4 items:\n";
|
|
forderange { print "@_\n" } 4;
|
|
printf "\n%3s %15s %15s\n","N","List count","!N";
|
|
printf "%3d %15d %15d %15d\n",$_,countderange($_),subfactorial1($_),subfactorial2($_) for 0..9;
|
|
printf "%3d %15s %s\n",$_,"",subfactorial2($_) for 20,200;
|