BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:

A problem in two parts:

  1. Code a (possibly recursive) solution to generalise the following "calculation".

    my $total = calcIt( $N, $depth );

  2. Define a formula for calculating the total without going through the motions.

    The innermost sum can be replaced by $_ * ( $_ + 1 ) / 2.

    Can the rest of the process be replaced by a formula in terms of $N & $depth?

I believe the values produced are related to Binomial coefficients C(n, d). of various dimensions--but that's where I get stuck. 

use List::Util qw[ sum ];

$N = 10; 
print sum map{ 
    sum map{ 
        sum map{ 
            sum map{ 
                sum map{ 
                    sum 0 .. $_ 
                } 0 .. $_ 
            } 0 .. $_ 
       } 0 .. $_ 
    } 0 .. $_ 
} 0 .. $N;;
11440

$N = 20; 
print sum map{ 
    sum map{ 
        sum map{ 
            sum map{ 
                sum map{ 
                    sum 0 .. $_ 
                } 0 .. $_ 
            } 0 .. $_ 
        } 0 .. $_ 
    } 0 .. $_ 
} 0 .. $N;;
657800

[download]
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Replies are listed 'Best First'.
Re: Math fun.
by ikegami (Patriarch) on Feb 13, 2007 at 18:51 UTC

    Part 1: 

    use strict;
use warnings;

use List::Util qw( sum );

sub calcIt {
   our $r;
   local $r = sub {
      my ($depth) = @_;
      if ($depth == 0) {
         return sum 1..$_;
      } else {
         return sum map { $r->($depth-1) } 1..$_;
      }
   };

   return $r->(5) for $_[0];
}

print(calcIt(10), "\n");  # 11440
print(calcIt(20), "\n");  # 657800

    [download]

    Part 1, with memoization 

    use strict;
use warnings;

use List::Util qw( sum );

{
   my %memoize;

   sub calcIt {
      our $r;
      local $r = sub {
         my ($depth) = @_;
         return $memoize{"$depth:$_"} ||= (
            ($depth
               ? sum map { $r->($depth-1) } 1..$_
               : $_ * ( $_ + 1 ) / 2
            )
         );
      };
      return $r->(5) for $_[0];
   }
}

print(calcIt(10), "\n");  # 11440
print(calcIt(20), "\n");  # 657800

    [download]

    Note: I changed 0.. to 1... You were adding way too many zeros.

[reply]
[d/l]
[select]
[reply]

        It's only compiled once, so it's not technically "thrown away". Only the reference to it is.

        I did it that way out of habit. Usually, the recursive bit would be a closure over args passed to the non-recursive bit. In this case, I didn't close over anything, so it doesn't need to be nested.

[reply]
Re: Math fun.
by ikegami (Patriarch) on Feb 13, 2007 at 20:29 UTC
    Part 2: 
    #
# Combination
#
#                 n!
#    C(n, r) = --------
#              r!(n-r)!
#

sub C {
   my ($n, $r) = @_;
   my $c = 1;
   $c *= $n--/$r-- for 1..$r;
   return $c;
}

sub calcIt {
   my ($n, $d) = @_;
   return C($n+$d+2-1, $d+2);
}

print(calcIt(10, 5), "\n");  # 11440
print(calcIt(20, 5), "\n");  # 657800

    [download]
[reply]
[d/l]
Re: Math fun.
by ikegami (Patriarch) on Feb 13, 2007 at 19:25 UTC

    Is this of any help? 

    $n\$d   1       2       3       4       5       6       7
1       1       1       1       1       1       1       1
2       4       5       6       7       8       9       10
3       10      15      21      28      36      45      55
4       20      35      56      84      120     165     220
5       35      70      126     210     330     495     715
6       56      126     252     462     792     1287    2002
7       84      210     462     924     1716    3003    5005
8       120     330     792     1716    3432    6435    11440
9       165     495     1287    3003    6435    12870   24310
10      220     715     2002    5005    11440   24310   48620
11      286     1001    3003    8008    19448   43758   92378
12      364     1365    4368    12376   31824   75582   167960
13      455     1820    6188    18564   50388   125970  293930
14      560     2380    8568    27132   77520   203490  497420
15      680     3060    11628   38760   116280  319770  817190
16      816     3876    15504   54264   170544  490314  1307504
17      969     4845    20349   74613   245157  735471  2042975
18      1140    5985    26334   100947  346104  1081575 3124550
19      1330    7315    33649   134596  480700  1562275 4686825
20      1540    8855    42504   177100  657800  2220075 6906900

    [download]

    The above was produced using the following program:

    Read more... (806 Bytes)

    You can really appreciate the effect of memoization here.

[reply]
[d/l]
[select]

      If you add a column of 1's on the left (and a column of sums of 1 .. N after the 1..N column), you get Pascal's triangle, and thus the link to combinatorics: 

      1   1   1    1     1     1     1     1     1     1
1   2   3    4     5     6     7     8     9     10
1   3   6    10    15    21    28    36    45    55
1   4   10   20    35    56    84    120   165   220
1   5   15   35    70    126   210   330   495   715
1   6   21   56    126   252   462   792   1287  2002
1   7   28   84    210   462   924   1716  3003  5005
1   8   36   120   330   792   1716  3432  6435  11440

      [download]

      Update: added missing 3rd column as per eric256's observation

      Fcn(D,N) => (5,10) seems to correspond to Choose(16,7) where Choose(n,k) is n!/k!(n-k)!

      Likewise, Fcn(5,20) seems to correspond to Choose(26,7).

      More generically, it looks like your function can be reduced to Choose(D+N+1,D+2)

      Of course, you still have recursion in the computation of the factorial, so I don't think you can quite avoid it entirely.

      -xdg

      Code written by xdg and posted on PerlMonks is public domain. It is provided as is with no warranties, express or implied, of any kind. Posted code may not have been tested. Use of posted code is at your own risk.

[reply]
[d/l]
        Aye, I've already posted that solution, with an efficient implementation.
[reply]

        That is not pascals triangle...if it were wouldn't it be symmetrical?

        1 1  1  1
1 2  3  4
1 3  6 10
1 4 10 20

        [download]

        ___________
        Eric Hodges
[reply]
[d/l]
Re: Math fun.
by suaveant (Parson) on Feb 13, 2007 at 20:11 UTC
    Good ole' Gauss
    http://mathforum.org/library/drmath/view/57919.html

    1 plus N quantity times N divided by 2.

    so 

    sum 1..100001 == 5000150001
#and
(100001+1)*(100001/2) == 5000150001

    [download]
    Doesn't help much in this, but is interesting nonetheless.

                    - Ant
                    - Some of my best work - (1 2 3)

[reply]
[d/l]
Re: Math fun.
by eric256 (Parson) on Feb 13, 2007 at 23:50 UTC

    Somewhere I missed what you are actualy trying to do. What is the problem? You mention CalcIt and have a bunch of sum and maps, but is there a definition of the formula you are trying to solve?


    ___________
    Eric Hodges
[reply]
      is there a definition of the formula you are trying to solve?

      No there isn't. That was part 2 of the problem. The bunch of sums and maps produces the results I require as verified by comparison against the results of exhuastive generation of the computation is summarises. I was looking to reduce the computationally intensive work involved in arriving at those results for higher values of $N & $depth.

      Or rather, there wasn't. However, ikegami has divined a generalized formula, which is what I was seeking.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
[select]

Back to Seekers of Perl Wisdom