blob: 16e60d1c82cf93a3e55d685f1a8a4dd2c2411920 (
plain) (
tree)
|
|
#!/usr/bin/env perl
use strict;
use warnings;
use 5.020;
use experimental 'signatures';
my %memoize;
sub sub_combinations($n, $max_val = $n) {
return 1 if $n == 0;
my $key = "$n,$max_val";
return $memoize{$key} if $memoize{$key};
my $combinations = 0;
for my $i (reverse 1..$n) {
next if $i > $max_val;
$combinations += __SUB__->($n - $i, $i);
}
$memoize{$key} = $combinations;
$combinations;
}
for my $i (2..100) {
say "$i: " . (sub_combinations($i) - 1);
}
__END__
# 1 1 2 3 5 8 13 21 34 55
# 1 3 6 10 15 21 28 36 45 55
# 1: 0 ( ) ( )
# 2: 1 ( 1) ( 1)
# 3: 2 ( 1+ 1) ( 1+ 1)
# 4: 4 ( 2+ 1+ 1) ( 1+ 2+ 1)
# 5: 6 ( 2+ 2+ 1+ 1) ( 1+ 2+ 2+ 1)
# 6: 10 ( 3+ 3+ 2+ 1+ 1) ( 1+ 2+ 3+ 3+ 1)
# 7: 14 ( 3+ 4+ 3+ 2+ 1+ 1) ( 1+ 2+ 3+ 4+ 3+ 1)
# 8: 21 ( 4+ 5+ 5+ 3+ 2+ 1+ 1) ( 1+ 2+ 3+ 5+ 5+ 4+ 1)
# 9: 29 ( 4+ 7+ 6+ 5+ 3+ 2+ 1+ 1) ( 1+ 2+ 3+ 5+ 6+ 7+ 4+ 1)
# 10: 41 ( 5+ 8+ 9+ 7+ 5+ 3+ 2+ 1+ 1) ( 1+ 2+ 3+ 5+ 7+ 9+ 8+ 5+ 1)
# 11: 54 ( 5+10+10+10+ 7+ 5+ 5+ 2+ 1+ 1) ( 1+ 2+ 3+ 5+ 7+ 9+11+11+ 6+ 1)
#
# 1 1
#
# 2 1
# 1 1 1
#
# 3 1
# 2 2
# 2 1 1
# 1 1 1 1
#
# 4 1
# 3 2
# 3 1 1
# 2 2 1
# 2 1 1 1
# 1 1 1 1 1
#
# 5 1
# 4 2
# 4 1 1
# 3 3
# 3 2 1
# 3 1 1 1
# 2 2 2
# 2 2 1 1
# 2 1 1 1 1
# 1 1 1 1 1 1
#
# 6 1
# 5 2
# 4 3
# 5 1 1
# 4 2 1
# 3 3 1
# 3 2 2
# 4 1 1 1
# 3 2 1 1
# 2 2 2 1
# 3 1 1 1 1
# 2 2 1 1 1
# 2 1 1 1 1 1
# 1 1 1 1 1 1 1
#
# 7 1
# 6 2
# 5 3
# 4 4
# 6 1 1
# 5 2 1
# 4 3 1
# 4 2 2
# 3 3 2
# 5 1 1 1
# 4 2 1 1
# 3 3 1 1
# 3 2 2 1
# 2 2 2 2
# 4 1 1 1 1
# 3 2 1 1 1
# 2 2 2 1 1
# 3 1 1 1 1 1
# 2 2 1 1 1 1
# 2 1 1 1 1 1 1
# 1 1 1 1 1 1 1 1
#
# 8 1
# 7 2
# 6 3
# 5 4
# 7 1 1
# 6 2 1
# 5 3 1
# 5 2 2
# 4 4 1
# 4 3 2
# 3 3 3
# 6 1 1 1
# 5 2 1 1
# 4 3 1 1
# 4 2 2 1
# 3 3 2 1
# 3 2 2 2
# 5 1 1 1 1
# 4 2 1 1 1
# 3 3 1 1 1
# 3 2 2 1 1
# 2 2 2 2 1
# 4 1 1 1 1 1
# 3 2 1 1 1 1
# 2 2 2 1 1 1
# 3 1 1 1 1 1 1
# 2 2 1 1 1 1 1
# 2 1 1 1 1 1 1 1
# 1 1 1 1 1 1 1 1 1
#
# 9 1
# 8 2
# 8 1 1
# 7 3
# 7 2 1
# 7 1 1 1
# 6 4
# 6 3 1
# 6 2 2
# 6 2 1 1
# 6 1 1 1 1
# 5 5
# 5 4 1
# 5 3 2
# 5 3 1 1
# 5 2 2 1
# 5 2 1 1 1
# 5 1 1 1 1 1
# 4 4 2
# 4 4 1 1
# 4 3 3
# 4 3 2 1
# 4 3 1 1 1
# 4 2 2 2
# 4 2 2 1 1
# 4 2 1 1 1 1
# 4 1 1 1 1 1 1
# 3 3 3 1
# 3 3 2 2
# 3 3 2 1 1
# 3 3 1 1 1 1
# 3 2 2 2 1
# 3 2 2 1 1 1
# 3 2 1 1 1 1 1
# 3 1 1 1 1 1 1 1
# 2 2 2 2 2
# 2 2 2 2 1 1
# 2 2 2 1 1 1 1
# 2 2 1 1 1 1 1 1
# 2 1 1 1 1 1 1 1 1
# 1 1 1 1 1 1 1 1 1 1
#
# 10 1
# 9 2
# 8 3
# 7 4
# 6 5
# 9 1 1
# 8 2 1
# 7 3 1
# 7 2 2
# 6 4 1
# 6 3 2
# 5 5 1
# 5 4 2
# 5 3 3
# 4 4 3
# 8 1 1 1
# 7 2 1 1
# 6 3 1 1
# 6 2 2 1
# 5 4 1 1
# 5 3 2 1
# 4 4 2 1
# 4 3 3 1
# 4 3 2 2
# 3 3 3 2
# 7 1 1 1 1
# 6 2 1 1 1
# 5 3 1 1 1
# 5 2 2 1 1
# 4 4 1 1 1
# 4 3 2 1 1
# 4 2 2 2 1
# 3 3 3 1 1
# 3 3 2 2 1
# 3 2 2 2 2
# 6 1 1 1 1 1
# 5 2 1 1 1 1
# 4 3 1 1 1 1
# 4 2 2 1 1 1
# 3 3 2 1 1 1
# 3 2 2 2 1 1
# 2 2 2 2 2 1
# 5 1 1 1 1 1 1
# 4 2 1 1 1 1 1
# 3 3 1 1 1 1 1
# 3 2 2 1 1 1 1
# 2 2 2 2 1 1 1
# 4 1 1 1 1 1 1 1
# 3 2 1 1 1 1 1 1
# 2 2 2 1 1 1 1 1
# 3 1 1 1 1 1 1 1
# 2 2 1 1 1 1 1 1
# 3 1 1 1 1 1 1 1 1
# 2 2 1 1 1 1 1 1 1
# 2 1 1 1 1 1 1 1 1 1
# 1 1 1 1 1 1 1 1 1 1 1
|