Re: Pascal triange...
by ton (Friar) on Jun 19, 2002 at 08:46 UTC
|
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!
-Ton
-----
Be bloody, bold, and resolute; laugh to scorn
The power of man... | [reply] [Watch: Dir/Any] [d/l] [select] |
|
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";
}
}
Abigail | [reply] [Watch: Dir/Any] [d/l] |
|
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;
}
}
Abigail
| [reply] [Watch: Dir/Any] [d/l] [select] |
|
|
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 :)
kiat
| [reply] [Watch: Dir/Any] |
|
|
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!!
kiat
| [reply] [Watch: Dir/Any] |
Re: Pascal triange...
by ariels (Curate) on Jun 19, 2002 at 09:09 UTC
|
As mentioned above, it's better to use Pascal's recurrence than the binomial formula. See this writeup (tye's).
| [reply] [Watch: Dir/Any] |
Re: Pascal's triangle...
by gumby (Scribe) on Jun 19, 2002 at 13:33 UTC
|
#!/usr/bin/perl -wl
sub pascal {
while (s/\d+(?= (\d+))/$&+$1/eg < shift) { s/^/1 /; print; }
}
Which is basically Re: Pascal triange... in essence. | [reply] [Watch: Dir/Any] [d/l] |
Re: Pascal triange...
by gumby (Scribe) on Jun 19, 2002 at 09:10 UTC
|
Using an approximation to Stirling's series:
use constant PI => 3.141592653589793238;
...
sub factorial {
my $n = shift;
return (sqrt((2*$n + 1/3)*PI)*($n**$n)*exp(-$n));
}
| [reply] [Watch: Dir/Any] [d/l] |
|
use constant PI => 3.141592653589793238;
since you're only calculating pi once, and inlining it, take advantage of the operating system's precision...
use constant PI => 4 * atan 1, 1;
## or as i prefer
# sub PI() { 4 * atan 1, 1 }
~Particle *accelerates*
| [reply] [Watch: Dir/Any] [d/l] [select] |
|
Or, to get rid of that nasty "4":
sub PI () { atan2 0, -1 }
-- Randal L. Schwartz, Perl hacker | [reply] [Watch: Dir/Any] [d/l] |
|
use Math::Complex;
use constant PI => pi();
# or just
pi();
jeffa
L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
B--B--B--B--B--B--B--B--
H---H---H---H---H---H---
(the triplet paradiddle with high-hat)
| [reply] [Watch: Dir/Any] [d/l] |
|
use constant PI => 3;
;-P
~Particle *accelerates*
| [reply] [Watch: Dir/Any] [d/l] [select] |
|
|
use constant PI => 4 * atan2 1, 1;
I can recall from memory more than 700 digits of pi ;-) | [reply] [Watch: Dir/Any] [d/l] |
|
BTW, that's the FPU's precision, not the OS's. (On machines that have an FPU, anyway.)
/me is pedantic sometimes
We are using here a powerful strategy of synthesis: wishful thinking. -- The Wizard Book
| [reply] [Watch: Dir/Any] |
|
Ok, it's been communicated that using the entropy function would provide a better approximation to nCr. So here is such a formula:
Let H(eps) := -eps.log_2(eps)-(1-eps)log_2(1-eps) be a binary entropy function.
Then binom(n, eps.n) is approximately equal to 2^(n.H(eps)).
Where eps is short for epsilon.
Update: Note that this uses the more common Stirling formula which is slightly less accurate as it truncates terms in the series (instead of approximating them like the formula i posted before).
| [reply] [Watch: Dir/Any] |
Re: Pascal's triangle...
by YuckFoo (Abbot) on Jun 20, 2002 at 19:59 UTC
|
I dug this nugget out of my snippets directory. It's not
mine and I don't know who to credit.
YuckFoo
#!/usr/bin/perl
while((@_=(1,map$_[$_-1]+$_[$_],1..@_))<=$ARGV[0]){print"@_\n"}
| [reply] [Watch: Dir/Any] [d/l] |
Re: Pascal triange...
by Zaxo (Archbishop) on Jun 19, 2002 at 09:16 UTC
|
sub pascal {
my ($rows) = @_
return $rows * ( $rows + 1 ) / 2;
}
</score>Update: Nevermind, I missed your intent.
After Compline, Zaxo | [reply] [Watch: Dir/Any] [d/l] |
Re: Pascal's triangle...
by Anonymous Monk on Dec 04, 2019 at 04:19 UTC
|
sub line {
my @a1 = @_;
my @b;
push @b, " 1";
push @b, $a1[$_] + $a1[ $_ - 1 ] foreach ( 1 .. $#a1 + 1 );
return @b;
}
my @b = qw(1 1);
my $s = 100;
print " " x ($s), " 1\n";
foreach ( 2 .. shift ) {
my $l = join " ", @b;
print " " x ( $s - ( length $l ) / 2 ), "$l\n";
@b = line(@b);
shift @b;
}
| [reply] [Watch: Dir/Any] [d/l] |