Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re: How to generate restricted partitions of an integer

by grinder (Bishop)
on Nov 11, 2004 at 12:05 UTC ( #407006=note: print w/replies, xml ) Need Help??


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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://407006]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (5)
As of 2020-10-21 07:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My favourite web site is:












    Results (212 votes). Check out past polls.

    Notices?