http://www.perlmonks.org?node_id=407006


in reply to How to generate restricted partitions of an integer

Here is my try to [solve] the puzzle

Heh, a fine example of Ken Thompson's adage "when in doubt, use brute force".

Your code does have the merit of being very straightforward to understand. If I had the tuits I would code up an iterator solution using the closure-as-odometer idiom, but the code would not be as clear.

A simple observation of your code is to note that many a time, the sum exceeds 100 way before you get down to the fifth inner loop. Therefore, exiting the loop early via last will save considerable amount of time:

my $cnt = 0; for my $f ( 0 .. 20 ) { for my $z ( 0 .. 10 ) { last if $f*5 + $z*10 > 100; for my $zw ( 0 .. 5 ) { last if $f*5 + $z*10 + $zw*20 > 100; for my $fu ( 0 .. 2 ) { last if $f*5 + $z*10 + $zw*20 + $fu*50 > 100; for my $hu ( 0 .. 1 ) { $cnt++ if $f * 5 + $z * 10 + $zw * 20 + $fu * 50 + $hu * 100 + == 100; } } } } } print $cnt;

You could unconditionally increment a counter in the inner loop inside this code and yours, and compare how many less times my inner loop gets called.

- another intruder with the mooring of the heart of the Perl

Replies are listed 'Best First'.
Re^2: How to generate restricted partitions of an integer
by tachyon (Chancellor) on Nov 11, 2004 at 14:13 UTC
    686 loops for yours. 8316 for the original. 197 for mine which uses a slightly more optimised fail fast.

      46 for mine :-)

      function calls, not loops though :-(

      Updated was 67 but I moved an if and reduced it to 46