P is for Practical PerlMonks

### Re: How to generate restricted partitions of an integer

by tachyon (Chancellor)
 on Nov 11, 2004 at 13:08 UTC ( #407021=note: print w/replies, xml ) Need Help??

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

cheers

tachyon

Create A New User
Node Status?
node history
Node Type: note [id://407021]
help
Chatterbox?
 [Discipulus]: ;=) [erix]: that's not a setter but a pointer [erix]: (but what's in a name?) Discipulus aka NodeReaper studying perlguts..

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (9)
As of 2017-05-24 07:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favorite model of computation is ...

Results (183 votes). Check out past polls.