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

The other day the topic of the binomial distribution came up. The binomial distribution is a part of probability theory and looks like this:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1

I thought writing a sub to generate this would be easy.....

So here is another hole. Rules:

(1) sub accepts one arg which corresponds to the number of levels to print;

(2) sub prints it out

(3) formating like this is OK

1 1 1 1 2 1 1 3 3 1 <- this is level 4 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1

(4) how about we use strict, just for something different

I have <70 chars, can you do better? I'll post mine in 2 days

tachyon

Replies are listed 'Best First'.
Re: Binomial Golf
by japhy (Canon) on May 30, 2001 at 08:32 UTC
    56 chars:
    # 123456789_123456789_123456789_123456789_123456789_123456 sub p {$_=pop;@_=(1,map$_[-2]+pop,0..$#_),print"@_\n"while$_>@_}


    japhy -- Perl and Regex Hacker
      My best was 59 characters:
      sub p { map{$_[$_]+=$_[$_+1]for 0..$#_;@_=(1,@_);print"@_\n"}1..pop }
      However, I can reduce japhy's solution from 56 to 45 characters:
      sub p { @_=(1,map$_[-2]+pop,@_),print"@_\n"for 1..pop }
      BTW, I find it amusing that monks are giving their golf subroutines one-letter names, when the subroutine name isn't counted in the length of the solution. :)

      I was considering sub pascal's_triangle {} for this one. ;)

Re: Binomial Golf
by gumpu (Friar) on May 30, 2001 at 11:16 UTC

    On a related note; a real challenge is also to just compute one of the entries in the table. Especially for higher values.

    If we number the table as follows:

    F 1 2 3 4 5 6 7 8 9 10 11 --> m 1 1 2 1 1 3 1 2 1 4 1 3 3 1 5 1 4 6 4 1 6 1 5 10 10 5 1 7 1 6 15 20 15 6 1 8 1 7 21 35 35 21 7 1 9 1 8 28 56 70 56 28 8 1 10 1 9 36 84 126 126 84 36 9 1 11 1 10 45 120 210 252 210 120 45 10 1 | n

    it can be said to define a function F(n,m). For instance:

    F(1,1) = 1 F(11,2) = 10 F(9,5) = 70

    However for higher values of n this function returns very large numbers around the point F(n,n/2). This are the numbers in the center of the table. For instance try computing F(400,200) or F(400,199).

    These numbers are so large they do not fit into a floatingpoint number. It's of course possible to use the BigInt package, but that slows down computation, and uses quite some memory. Hence just printing the table for large values of n becomes impossible.

    However the numbers around F(n,n), and F(n,1) stay pretty small for large n and could be computed. These are the numbers at the edge of the table. For instance F(400,1) = F(400,400) = 1, and even F(400,5) is computable.

    Finding F(n,m) is useful for several statistical and counting problems. However writing a program that efficiently computes F(n,m) for any n,m, is quite a challenge! (At least I found it quite a challenge when I tried to write one.) One approach is to 'walk' the edge of the table towards the entry that needs to be computed. Thereby avoiding the center of the table with all the giant numbers. But there must be a more effecient way to compute F .... any suggestions?

    Have Fun

      Check the thread Binomial Expansion there's a really interesting n choose r sub there by ariels and a proof underneath by japhy. (Among other things)
      # copy of said subroutine sub nCr { my ($n, $r) = @_; my $res = 1; for my $i (1..$r) { $res *= $n--; $res /= $i; } $res; }

        Thanks! That's a very elegant solution. I spend a day or so comming up with a program to do the same. And that was about a page long. Very nifty.

        Have Fun

Re: Binomial Golf
by MeowChow (Vicar) on May 31, 2001 at 00:38 UTC
    39 chars:
    sub p { @_=map$_+pop,@_,print"1 @_\n"for 1..pop }
       MeowChow                                   
                   s aamecha.s a..a\u$&owag.print
Re: Binomial Golf
by Arguile (Hermit) on May 30, 2001 at 14:37 UTC

    A full 14 chars over japhy's, with a total of 70 looks like I'm over par for the course :)

    # 789_123 +456789_ # 123456789_123456789_123456789_123456789_123456789_123456!!!!!!! +!!!!!!! sub p {@_=(1,@_);for(1..pop){print"@_\n";map{$_=abs;$_[$_+1]+=$_[$_]}- +$#_..0}}
Re: Binomial Golf
by tachyon (Chancellor) on May 31, 2001 at 06:00 UTC

    Damn, drat, blast, gadzooks, foiled again. MeowChow not only comes up with a similar method but beats me by 4 charachters to boot!!! Using the true return from print to add a '1' to the array is really clever coding MC.

    tachyon

    &b(10); &binomial(10); # my simple sub sub binomial { for(0..pop){ my $last = 0; for (@_){ my $temp = $_; $_ += $last; $last = $temp; } push@_,1; print"@_\n"; } } # my golf progression sub b { #map{my$l;map{$t=$_;$_+=$l;$l=$t}@_;push@_,1;print"@_\n"}0..pop; #map{my$l;map{($l,$_)=($_,$_+$l)}@_;push@_,1;print"@_\n"}0..pop; #map{print"1 @_\n";push@_,map{$_+pop}@_,1}0..pop map{print"1 @_\n";@_=map{$_+pop}@_,1}0..pop } $\=$"; sub AUTOLOAD{@_ =caller();print shift} { package Back; ::()} { package To; &::() } { package The; &::() } { package Drawing;&::} { package Board; ::()}