Problems? Is your data what you think it is? PerlMonks

### Perl, please do my math homework

by whakka (Hermit)
 on Oct 18, 2009 at 05:17 UTC ( #801833=CUFP: print w/replies, xml ) Need Help??

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/;
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.

Replies are listed 'Best First'.
Re: Perl, please do my math homework
by omouse (Initiate) on Nov 15, 2009 at 06:44 UTC
You should learn Common Lisp. It has this neat function/macro called TRACE that will automatically show the input of every call to whatever function you're tracing. Everytime I've debugged recursive functions I've used it.

Create A New User
Node Status?
node history
Node Type: CUFP [id://801833]
Approved by planetscape
Front-paged by planetscape
help
Chatterbox?
 [LanX]: ther is also Dist::Zilla :-/ [LanX]: [Your Mother]: Dist::Zilla is kind of the nuclear option. I set it up back in the day but it's really targeted at authors who are managing MANY modules and want to automate everything. [erix]: perlancar should know ;) [LanX]: see warning [Your Mother]: Thanks for the warning notice. [LanX]: :p [LanX]: confusing sh+t [Your Mother]: Yes.

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (7)
As of 2017-08-18 17:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (306 votes). Check out past polls.

Notices?