In the course of my math class in the engineering program I'm currently in it's often convenient to write up little programs that perform some calculation based on a function or algorithm. However, oftentimes a reasonable program makes calculations in a different way than humans might, and it becomes a challenge to parse the
print statements I insert into the code to "show my work."
Well I finally decided to get around this problem after reading about inlining eval's in regular expressions while reading the Camel in a compromising position recently and faced with a particularly laborious exercise in my latest assignment:
Find the number of partitions of 7 and 8 using the formula for the number of partitions of a number (all possible combinations of adding smaller positive integers):
P(m,n) = {
1 if m or n = 1,
P(m,m) if m < n,
1 + P(m,m-1) if m = n > 1,
P(m,n-1) + P(m-n,n) if m > n > 1
}
My first attempt was straightforward:
sub partition {
my ( $m, $n ) = @_;
die "bad inputs" if $m <= 0 or $n <= 0;
print "P($m,$n) = ";
if ( $m == 1 or $n == 1 ) {
say 1;
return 1;
}
if ( $m < $n ) {
say "P($m,$m)";
return partition( $m, $m );
}
if ( $m == $n ) {
say "1 + P($m,", $m - 1, ")";
return 1 + partition( $m, $m - 1 );
}
if ( $m > $n ) {
say "P($m,", $n - 1, ") + P(", $m - $n, ",$n)";
return partition( $m, $n - 1 ) + partition( $m - $n, $n );
}
die "impossible!";
}
MAIN: {
my ( $m, $n ) = @ARGV;
$n ||= $m;
say partition( $m, $n );
}
The output to this program though is actually harder to put together than doing the problem manually! The recursion is depth-first and so the program goes straight to the bottom of each branch, and yet it's more natural to evaluate one level at a time and combine. Fortunately, Perl rocks my world:
sub P {
# Returns strings!
my ( $m, $n ) = @_;
if ( $m == 1 or $n == 1 ) {
return 1;
}
if ( $m < $n ) {
return "P($m,$m)";
}
if ( $m == $n ) {
return sprintf( "1 + P(%i,%i)", $m, $m - 1 );
}
if ( $m > $n ) {
return sprintf( "P(%i,%i) + P(%i,%i)", $m, $n - 1, $m - $n, $n
+ );
}
die "impossible!";
}
MAIN: {
local $_ = "P($m,$n)";
print;
while ( /\D/ ) {
# Put ints up front
1 while s/^(.+\)) \+ (\d+)/$2 + $1/;
# Add the ints
1 while s/(\d+) \+ (\d+)/$1 + $2/eg;
# Evaluate *one* level at a time
s/(P\(\d+,\d+\))/$1/eeg;
printf( "\n = %s", $_ );
}
}
And the output looks like:
$ partition.pl 7
P(7,7)
= 1 + P(7,6)
= 1 + P(7,5) + P(1,6)
= 1 + P(7,4) + P(2,5) + 1
= 2 + P(7,3) + P(3,4) + P(2,2)
= 2 + P(7,2) + P(4,3) + P(3,3) + 1 + P(2,1)
= 3 + P(7,1) + P(5,2) + P(4,2) + P(1,3) + 1 + P(3,2) + 1
= 5 + 1 + P(5,1) + P(3,2) + P(4,1) + P(2,2) + 1 + P(3,1) + P(1,2)
= 7 + 1 + P(3,1) + P(1,2) + 1 + 1 + P(2,1) + 1 + 1
= 12 + 1 + 1 + 1
= 15
Beautiful! Copied straight to the notebook.
Update: For those interested in efficient solutions to this and other integer partition problems, Limbic~Region has this post.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.