in reply to
How to generate restricted partitions of an integer
This reduces the 8316 loops your code requires to 197 which is almost 2 orders of magnitude faster tahn your original and 3.5x faster than grinders example that needs 686 loops. Only 4:1 wastage on the test is pretty good as semi brute force goes and certainly beats the original 166:1. All it does different is to limit the looping to the limited subset of possible cases....
my ( $loops, $cnt );
printf "%4d %4d %4d %4d %4d\n", 100,50,20,10,5;
for (my $e5=0; $e5<=100; $e5+=10 ) {
for (my $e10=0; $e10<=100-$e5; $e10+=10 ) {
for (my $e20=0; $e20<=100-$e10-$e5; $e20+=20 ) {
for (my $e50=0; $e50<=100-$e20-$e10-$e5; $e50+=50 ) {
for (my $e100=0; $e100<=100-$e50-$e20-$e10-$e5; $e100+=100 ) {
$loops++;
if ( $e5+$e10+$e20+$e50+$e100 == 100 ) {
printf "%4d %4d %4d %4d %4d\n",$e100/100,$e50/50,$e20/20,$
+e10/10,$e5/5;
$cnt++;
}
}
}
}
}
}
print "\n$cnt possibilities in $loops loops\n";
__DATA__
100 50 20 10 5
1 0 0 0 0
0 2 0 0 0
0 0 5 0 0
0 1 2 1 0
0 0 4 2 0
0 1 1 3 0
0 0 3 4 0
0 1 0 5 0
0 0 2 6 0
0 0 1 8 0
0 0 0 10 0
0 1 2 0 2
0 0 4 1 2
0 1 1 2 2
0 0 3 3 2
0 1 0 4 2
0 0 2 5 2
0 0 1 7 2
0 0 0 9 2
0 0 4 0 4
0 1 1 1 4
0 0 3 2 4
0 1 0 3 4
0 0 2 4 4
0 0 1 6 4
0 0 0 8 4
0 1 1 0 6
0 0 3 1 6
0 1 0 2 6
0 0 2 3 6
0 0 1 5 6
0 0 0 7 6
0 0 3 0 8
0 1 0 1 8
0 0 2 2 8
0 0 1 4 8
0 0 0 6 8
0 1 0 0 10
0 0 2 1 10
0 0 1 3 10
0 0 0 5 10
0 0 2 0 12
0 0 1 2 12
0 0 0 4 12
0 0 1 1 14
0 0 0 3 14
0 0 1 0 16
0 0 0 2 16
0 0 0 1 18
0 0 0 0 20
50 possibilities in 197 loops
