Catalan numbers/Pascal's triangle: Difference between revisions
(→{{header|REXX}}: added a 3rd REXX version that used binomial coefficients.) |
(→{{header|REXX}}: added a version with memoization.) |
||
Line 491: | Line 491: | ||
/*──────────────────────────────────COMB (binomial coefficient) function*/ |
/*──────────────────────────────────COMB (binomial coefficient) function*/ |
||
comb: procedure; parse arg x,y; if x=y then return 1; if y>x then return 0 |
comb: procedure; parse arg x,y; if x=y then return 1; if y>x then return 0 |
||
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</lang> |
|||
'''output''' is the same as the 1<sup>st</sup> version. |
|||
===binomial coeff., memoized=== |
|||
This REXX version uses memoization for the calculation of factorials. |
|||
<lang rexx>/*REXX program obtains/displays Catalan numbers from Pascal's triangle.*/ |
|||
parse arg N .; if N=='' then N=15 /*Any args? No, then use default*/ |
|||
numeric digits max(9,N*4) /*can handle huge Catalan numbers*/ |
|||
!.=. |
|||
do j=1 for N |
|||
say comb(j+j,j) - comb(j+j,j-1) /*display the Jth Catalan number.*/ |
|||
end /*j*/ |
|||
exit /*stick a fork in it, we're done.*/ |
|||
/*──────────────────────────────────! (factorial) function──────────────*/ |
|||
!: procedure expose !.; parse arg z; if !.z\==. then return !.z; _=1 |
|||
do j=1 for arg(1); _=_*j; end; !.z=_; return _ |
|||
/*──────────────────────────────────COMB (binomial coefficient) function*/ |
|||
comb: procedure expose !.; parse arg x,y; if x=y then return 1 |
|||
if y>x then return 0 |
|||
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</lang> |
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</lang> |
||
'''output''' is the same as the 1<sup>st</sup> version. <br> |
'''output''' is the same as the 1<sup>st</sup> version. <br> |
Revision as of 22:35, 20 October 2014
You are encouraged to solve this task according to the task description, using any language you may know.
The task is to print out the first 15 Catalan numbers by extracting them from Pascal's triangle, see Catalan Numbers and the Pascal Triangle.
Ada
Uses package Pascal from the Pascal triangle solution[[1]]
<lang Ada>with Ada.Text_IO, Pascal;
procedure Catalan is
Last: Positive := 15; Row: Pascal.Row := Pascal.First_Row(2*Last+1);
begin
for I in 1 .. Last loop Row := Pascal.Next_Row(Row); Row := Pascal.Next_Row(Row); Ada.Text_IO.Put(Integer'Image(Row(I+1)-Row(I+2))); end loop;
end Catalan;</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
AutoHotkey
<lang AutoHotkey>/* Generate Catalan Numbers // // smgs: 20th Feb, 2014
- /
Array := [], Array[2,1] := Array[2,2] := 1 ; Array inititated and 2nd row of pascal's triangle assigned INI := 3 ; starts with calculating the 3rd row and as such the value Loop, 31 ; every odd row is taken for calculating catalan number as such to obtain 15 we need 2n+1 { if ( A_index > 2 ) { Loop, % A_INDEX { old := ini-1, index := A_index, index_1 := A_index + 1 Array[ini, index_1] := Array[old, index] + Array[old, index_1] Array[ini, 1] := Array[ini, ini] := 1 line .= Array[ini, A_index] " " } ;~ MsgBox % line ; gives rows of pascal's triangle ; calculating every odd row starting from 1st so as to obtain catalan's numbers if ( mod(ini,2) != 0) { StringSplit, res, line, %A_Space% ans := res0//2, ans_1 := ans++ result := result . res%ans_1% - res%ans% " " } line := ini++ } } MsgBox % result</lang>
- Produces:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
C++
<lang cpp>// Generate Catalan Numbers // // Nigel Galloway: June 9th., 2012 //
- include <iostream>
int main() {
const int N = 15; int t[N+2] = {0,1}; for(int i = 1; i<=N; i++){ for(int j = i; j>1; j--) t[j] = t[j] + t[j-1]; t[i+1] = t[i]; for(int j = i+1; j>1; j--) t[j] = t[j] + t[j-1]; std::cout << t[i+1] - t[i] << " "; } return 0;
}</lang>
- Produces:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
D
<lang d>void main() {
import std.stdio;
enum uint N = 15; uint[N + 2] t; t[1] = 1;
foreach (immutable i; 1 .. N + 1) { foreach_reverse (immutable j; 2 .. i + 1) t[j] += t[j - 1]; t[i + 1] = t[i]; foreach_reverse (immutable j; 2 .. i + 2) t[j] += t[j - 1]; write(t[i + 1] - t[i], ' '); }
}</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Icon and Unicon
The following works in both languages. It avoids computing elements in Pascal's triangle that aren't used.
<lang unicon>link math
procedure main(A)
limit := (integer(A[1])|15)+1 every write(right(binocoef(i := 2*seq(0)\limit,i/2)-binocoef(i,i/2+1),30))
end</lang>
Sample run:
->cn 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 ->
J
<lang j> Catalan=. }:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</lang>
- Example use:
<lang j> Catalan 15 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</lang>
A structured derivation of Catalan follows:
<lang j> o=. @: NB. Composition of verbs (functions)
( PascalTriangle=. i. ((+/\@]^:[)) #&1 ) 5
1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 1 5 15 35 70
( MiddleDiagonal=. (<0 1)&|: ) o PascalTriangle 5
1 2 6 20 70
( AdjacentLeft=. MiddleDiagonal o (2&|.) ) o PascalTriangle 5
1 4 15 1 5
( Catalan=. }: o (}. o MiddleDiagonal - }: o AdjacentLeft) o PascalTriangle o (2&+) f. ) 5
1 2 5 14 42
Catalan
}:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</lang>
jq
The first identity (C(2n,n) - C(2n, n-1)) given in the reference is used, as required by the task description, but see Catalan_numbers#jq for better alternatives.
Warning: jq uses IEEE 754 64-bit arithmetic, so the algorithm used here for Catalan numbers loses precision for n > 30 and fails completely for n > 510. <lang jq>def binomial(n; k):
if k > n / 2 then binomial(n; n-k) else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i) end;
def catalan_by_pascal: . as $n | binomial(2*$n; $n) - binomial(2*$n; $n-1);</lang>
Example:
(range(0;16), 30, 31, 510, 511) | [., catalan_by_pascal]
- Output:
<lang sh>$ jq -n -c -f Catalan_numbers_Pascal.jq [0,0] [1,1] [2,2] [3,5] [4,14] [5,42] [6,132] [7,429] [8,1430] [9,4862] [10,16796] [11,58786] [12,208012] [13,742900] [14,2674440] [15,9694845] [30,3814986502092304] [31,14544636039226880] [510,5.491717746183512e+302] [511,null]</lang>
Mathematica
This builds the entire Pascal triangle that's needed and holds it in memory. Very inefficienct, but seems to be what is asked in the problem. <lang Mathematica>nextrow[lastrow_] := Module[{output},
output = ConstantArray[1, Length[lastrow] + 1]; Do[ outputi + 1 = lastrowi + lastrowi + 1; , {i, 1, Length[lastrow] - 1}]; output ]
pascaltriangle[size_] := NestList[nextrow, {1}, size] catalannumbers[length_] := Module[{output, basetriangle},
basetriangle = pascaltriangle[2 length]; list1 = basetriangle# *2 + 1, # + 1 & /@ Range[length]; list2 = basetriangle# *2 + 1, # + 2 & /@ Range[length]; list1 - list2 ]
(* testing *) catalannumbers[15]</lang>
- Output:
{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845}
MATLAB / Octave
<lang MATLAB>p = pascal(17); diag(p(2:end-1,2:end-1))-diag(p,2)</lang> Output:
ans = 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Nimrod
<lang nimrod>const n = 15 var t = newSeq[int](n + 2)
t[1] = 1 for i in 1..n:
for j in countdown(i, 1): t[j] += t[j-1] t[i+1] = t[i] for j in countdown(i+1, 1): t[j] += t[j-1] stdout.write t[i+1] - t[i], " "</lang>
Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Pascal
<lang pascal>type
tElement = Uint64;
var
Catalan : array[0..50] of tElement;
procedure GetCatalan(L:longint); var
PasTri : array[0..100] of tElement; j,k: longInt;
begin
l := l*2; PasTri[0] := 1; j := 0; while (j<L) do begin inc(j); k := (j+1) div 2; PasTri[k] :=PasTri[k-1]; For k := k downto 1 do inc(PasTri[k],PasTri[k-1]); IF NOT(Odd(j)) then begin k := j div 2; Catalan[k] :=PasTri[k]-PasTri[k-1]; end; end;
end;
var
i,l: longint;
Begin
l := 15; GetCatalan(L); For i := 1 to L do Writeln(i:3,Catalan[i]:20);
end.</lang>
1 1 2 2 3 5 4 14 5 42 6 132 7 429 8 1430 9 4862 10 16796 11 58786 12 208012 13 742900 14 2674440 15 9694845
PARI/GP
<lang parigp>vector(15,n,binomial(2*n,n)-binomial(2*n,n+1))</lang>
- Output:
%1 = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
Perl
<lang Perl>use constant N => 15; my @t = (0, 1); for(my $i = 1; $i <= N; $i++) {
for(my $j = $i; $j > 1; $j--) { $t[$j] += $t[$j-1] } $t[$i+1] = $t[$i]; for(my $j = $i+1; $j>1; $j--) { $t[$j] += $t[$j-1] } print $t[$i+1] - $t[$i], " ";
}</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
After the 28th Catalan number, this overflows 64-bit integers. We could add use bigint; use Math::GMP ":constant"; to make it work, albeit not at a fast pace. However we can use a module to do it much faster:
<lang Perl>use ntheory qw/binomial/; print join(" ", map { binomial( 2*$_, $_) / ($_+1) } 1 .. 1000), "\n";</lang>
The Math::Pari module also has a binomial, but isn't as fast and overflows its stack after 3400.
Perl 6
<lang perl6>constant @pascal = [1], -> @p { [0, @p Z+ @p, 0] } ... *;
constant @catalan = gather for 2, 4 ... * -> $ix {
my @row := @pascal[$ix]; my $mid = +@row div 2; take [-] @row[$mid, $mid+1]
}
.say for @catalan[^20];</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 6564120420
PicoLisp
<lang PicoLisp>(de bino (N K)
(let f '((N) (if (=0 N) 1 (apply * (range 1 N))) ) (/ (f N) (* (f (- N K)) (f K)) ) ) )
(for N 15
(println (- (bino (* 2 N) N) (bino (* 2 N) (inc N)) ) ) )
(bye)</lang>
Python
<lang python>>>> n = 15 >>> t = [0] * (n + 2) >>> t[1] = 1 >>> for i in range(1, n + 1): for j in range(i, 1, -1): t[j] += t[j - 1] t[i + 1] = t[i] for j in range(i + 1, 1, -1): t[j] += t[j - 1] print(t[i+1] - t[i], end=' ')
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
>>> </lang>
<lang python>def catalan_number(n):
nm = dm = 1 for k in range(2, n+1): nm, dm = ( nm*(n+k), dm*k ) return nm/dm
print [catalan_number(n) for n in range(1, 16)]
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</lang>
Racket
<lang Racket>
- lang racket
(define (next-half-row r)
(define r1 (for/list ([x r] [y (cdr r)]) (+ x y))) `(,(* 2 (car r1)) ,@(for/list ([x r1] [y (cdr r1)]) (+ x y)) 1 0))
(let loop ([n 15] [r '(1 0)])
(cons (- (car r) (cadr r)) (if (zero? n) '() (loop (sub1 n) (next-half-row r)))))
- -> '(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900
- 2674440 9694845)
</lang>
REXX
explicit subscripts
<lang rexx>/*REXX program obtains Catalan numbers from Pascal's triangle. */ parse arg N .; if N== then N=15 /*Any args? No, then use default*/ numeric digits max(9,N%2+N%8) /*can handle huge Catalan numbers*/ @.=0; @.1=1 /*stem array default; 1st value.*/
do i=1 for N; ip=i+1 do j=i by -1 for N; jm=j-1; @.j=@.j+@.jm; end /*j*/ @.ip=@.i; do k=ip by -1 for N; km=k-1; @.k=@.k+@.km; end /*k*/ say @.ip-@.i /*display the Ith Catalan number.*/ end /*i*/ /*stick a fork in it, we're done.*/</lang>
output when using the default input:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
implicit subscripts
<lang rexx>/*REXX program obtains/displays Catalan numbers from Pascal's triangle.*/ parse arg N .; if N== then N=15 /*Any args? No, then use default*/ numeric digits max(9,N%2+N%8) /*can handle huge Catalan numbers*/ @.=0; @.1=1 /*stem array default; 1st value.*/
do i=1 for N; ip=i+1 do j=i by -1 for N; @.j=@.j+@(j-1); end /*j*/ @.ip=@.i; do k=ip by -1 for N; @.k=@.k+@(k-1); end /*k*/ say @.ip-@.i /*display the Ith Catalan number.*/ end /*i*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────@ subroutine────────────────────────*/ @: parse arg !; return @.! /*return the value of @.[arg(1)]*/</lang> output is the same as the 1st version.
using binomial coefficients
<lang rexx>/*REXX program obtains/displays Catalan numbers from Pascal's triangle.*/ parse arg N .; if N== then N=15 /*Any args? No, then use default*/ numeric digits max(9,N*4) /*can handle huge Catalan numbers*/
do j=1 for N /* [↓] show N Catalan numbers*/ say comb(j+j,j) - comb(j+j,j-1) /*display the Jth Catalan number.*/ end /*j*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────! (factorial) function──────────────*/ !: procedure; parse arg z; _=1; do j=1 for arg(1); _=_*j; end; return _ /*──────────────────────────────────COMB (binomial coefficient) function*/ comb: procedure; parse arg x,y; if x=y then return 1; if y>x then return 0 if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</lang> output is the same as the 1st version.
binomial coeff., memoized
This REXX version uses memoization for the calculation of factorials. <lang rexx>/*REXX program obtains/displays Catalan numbers from Pascal's triangle.*/ parse arg N .; if N== then N=15 /*Any args? No, then use default*/ numeric digits max(9,N*4) /*can handle huge Catalan numbers*/ !.=.
do j=1 for N say comb(j+j,j) - comb(j+j,j-1) /*display the Jth Catalan number.*/ end /*j*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────! (factorial) function──────────────*/ !: procedure expose !.; parse arg z; if !.z\==. then return !.z; _=1
do j=1 for arg(1); _=_*j; end; !.z=_; return _
/*──────────────────────────────────COMB (binomial coefficient) function*/
comb: procedure expose !.; parse arg x,y; if x=y then return 1
if y>x then return 0
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</lang>
output is the same as the 1st version.
Run BASIC
<lang runbasic>n = 15 dim t(n+2) t(1) = 1 for i = 1 to n
for j = i to 1 step -1 : t(j) = t(j) + t(j-1): next j t(i+1) = t(i) for j = i+1 to 1 step -1: t(j) = t(j) + t(j-1 : next j
print t(i+1) - t(i);" "; next i</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Ruby
<lang tcl>def catalan(num)
t = [0, 1] #grows as needed 1.upto(num).map do |i| i.downto(1){|j| t[j] += t[j-1]} t[i+1] = t[i] (i+1).downto(1) {|j| t[j] += t[j-1]} t[i+1] - t[i] end
end
puts catalan(15).join(", ")</lang>
- Output:
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845
VBScript
To run in console mode with cscript. <lang vbscript>dim t() if Wscript.arguments.count=1 then
n=Wscript.arguments.item(0)
else
n=15
end if redim t(n+1) 't(*)=0 t(1)=1 for i=1 to n
ip=i+1 for j = i to 1 step -1 t(j)=t(j)+t(j-1) next 'j t(i+1)=t(i) for j = i+1 to 1 step -1 t(j)=t(j)+t(j-1) next 'j Wscript.echo t(i+1)-t(i)
next 'i</lang>
Seed7
<lang seed7>$ include "seed7_05.s7i";
const proc: main is func
local const integer: N is 15; var array integer: t is [] (1) & N times 0; var integer: i is 0; var integer: j is 0; begin for i range 1 to N do for j range i downto 2 do t[j] +:= t[j - 1]; end for; t[i + 1] := t[i]; for j range i + 1 downto 2 do t[j] +:= t[j - 1]; end for; write(t[i + 1] - t[i] <& " "); end for; writeln; end func;</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Tcl
<lang tcl>proc catalan n {
set result {} array set t {0 0 1 1} for {set i 1} {[set k $i] <= $n} {incr i} {
for {set j $i} {$j > 1} {} {incr t($j) $t([incr j -1])} set t([incr k]) $t($i) for {set j $k} {$j > 1} {} {incr t($j) $t([incr j -1])} lappend result [expr {$t($k) - $t($i)}]
} return $result
}
puts [catalan 15]</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
zkl
using binomial coefficients.
<lang zkl>fcn binomial(n,k){ (1).reduce(k,fcn(p,i,n){ p*(n-i+1)/i },1,n) } (1).pump(15,List,fcn(n){ binomial(2*n,n)-binomial(2*n,n+1) })</lang>
- Output:
L(1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845)