Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine

Re: Pascal triange...

by ton (Friar)
on Jun 19, 2002 at 08:46 UTC ( #175591=note: print w/replies, xml ) Need Help??

in reply to Pascal's triangle...

Hey kiat,
I noticed that your algorithm skips the "1 1" row. I made some changes to fix that bug:
sub pascal { my ($rows) = @_; print "1\n"; for (my $outer = 1; $outer < $rows; $outer++) { my $inner = $outer; print "1"; for ($i = 1; $i < $inner; $i++) { my $denominator = factorial($i)*(factorial($inner-$i)); my $pascalnum = factorial($inner)/$denominator if ($denominator +!= 0); print " $pascalnum" if ($outer > 1); } print " 1\n"; } }
I also think that using the Binomial Theorem when printing out an entire Pascal's triangle is inefficient. I would rather add numbers from the previous row, as this is much, much faster for large numbers of rows. So I wrote up some code to do this:
sub ton_pascal { my $rows = shift; my $last_row = [ ]; my $this_row = [ 1 ]; last unless ($rows > 0); print "1\n"; for (my $i = 1; $i < $rows; ++$i) { $last_row = $this_row; $this_row = [ 1 ]; for (my $j = 1; $j < $i; $j++) { push(@$this_row, $last_row->[$j - 1] + $last_row->[$j]); } push(@$this_row, 1); print join(' ', @$this_row) . "\n"; } }
I'm using array references instead of arrays for extra speed (when we copy the results of $this_row into $last_row), but the references could be removed without affecting the algorithm.

Hope this was helpful... I had fun coding up ton_pascal, so thanks for the problem!

Be bloody, bold, and resolute; laugh to scorn
The power of man...

Replies are listed 'Best First'.
Re: Pascal triange...
by Abigail-II (Bishop) on Jun 19, 2002 at 11:48 UTC
    No need to copy rows. Here's a much smaller function:
    sub pascal { my @row; foreach (1 .. shift) { push @row => 1; $row [$_] += $row [$_ - 1] for reverse 1 .. @row - 2; print "@row\n"; } }


      Here's a variation on the theme. The difference is that this version doesn't change @row using pushes. It's going to be sized right the first time.
      sub pascal { my @row = (0) x $_ [0]; $row [0] = 1; foreach (1 .. shift) { print "@row[0 .. $_ - 1]\n"; $row [$_] += $row [$_ - 1] for reverse 1 .. @row; } }


        Maybe we can add space padding to your function :)
        sub pascal { my $max = shift or return; my @row = (0) x $max; $row[0] = 1; foreach (1 .. $max) { print " " x ($max - $_),"@row[0 .. $_ - 1]\n"; $row[$_] += $row[$_ - 1] for reverse 1 .. @row; } }
      Hello! Abigail-II,

      I like your smaller function (it's really elegant) but I don't understand how it works, even though it's only a few lines. Could you explain the parts to me?

      Thanks in anticipation :)

        It's not hard to see how it works. First thing to realize that one way of calculating the next line in the triangle is to take the previous line twice, shift one of the line one position to the right, and then add the elements piecewise. For instance:
            1  3  3  1
               1  3  3  1
            ------------- +
            1  4  6  4  1
        But if you look carefully, you see that to each element, we add the element to the left of it, except for the two elements on the far ends - which will both be one (a "new" 1 on the right, and the one of the left remains "as is").

        And that's how the program works. We first add a new element (with the push), then for each element, we add the preceding one. We have to work backwards of course, which is achieved by the reverse.


Re: Re: Pascal triangle...
by kiat (Vicar) on Jun 19, 2002 at 10:52 UTC
    Hello! Ton,

    Thanks for the correction on the double '1' !

    I just ran your code and it works perfectly - it's not only more elegant but also more efficient. It helps me see how the same problem can be solved by looking at it another way. Thanks!!


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://175591]
[1nickt]: marto would like to hear that. Of course he speaks very deliberately and dramatically, allowing pauses between words, so if anybody could pull it off it would be him, or someone impersonating him ...
[Eily]: Discipulus that's a chess joke BTW right? Because bishops don't walk straight :D
[choroba]: stop making chessy jokes about bishops!
[choroba]: I mean cheesy
[LanX]: lol
[ambrus]: no, the chess bishop itself is a joke on real bi-shops
[ambrus]: or at least on the stereotype of bi-shops
[choroba]: we call chess bishops "archers"
[Eily]: choroba sorry, I had to get that off my chess
[ambrus]: chess certainly hasn't started those stereotypes, like how kings aren't that powerful but has convinced their whole country to work for them, etc. it's just poured them to a nice clean form that would easily get propagated.

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (13)
As of 2017-09-26 12:15 GMT
Find Nodes?
    Voting Booth?
    During the recent solar eclipse, I:

    Results (294 votes). Check out past polls.