Catalan numbers/Pascal's triangle: Difference between revisions
No edit summary |
m →{{header|REXX}}: fixed handling of default args, changed/added comments and whitespace. |
||
Line 1,174: | Line 1,174: | ||
<lang rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
<lang rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
||
parse arg N . /*Obtain the optional argument from CL.*/ |
parse arg N . /*Obtain the optional argument from CL.*/ |
||
if N=='' | N==" |
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
||
numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/ |
numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/ |
||
@.=0; @.1=1 /*stem array default; define 1st value.*/ |
@.=0; @.1=1 /*stem array default; define 1st value.*/ |
||
do i=1 for N; ip=i+1 |
do i=1 for N; ip=i+1 |
||
do j=i by -1 for N; jm=j-1; @.j=@.j+@.jm; end /*j*/ |
do j=i by -1 for N; jm=j-1; @.j=@.j+@.jm; end /*j*/ |
||
⚫ | |||
@.ip=@.i |
|||
⚫ | |||
say @.ip - @.i /*display the Ith Catalan number. */ |
say @.ip - @.i /*display the Ith Catalan number. */ |
||
end /*i*/ /*stick a fork in it, we're all done. */</lang> |
end /*i*/ /*stick a fork in it, we're all done. */</lang> |
||
Line 1,206: | Line 1,205: | ||
<lang rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
<lang rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
||
parse arg N . /*Obtain the optional argument from CL.*/ |
parse arg N . /*Obtain the optional argument from CL.*/ |
||
if N=='' | N==" |
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
||
numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/ |
numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/ |
||
@.=0; @.1=1 /*stem array default; define 1st value.*/ |
@.=0; @.1=1 /*stem array default; define 1st value.*/ |
||
⚫ | |||
do |
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*/ |
|||
@.ip |
say @.ip - @.i /*display the Ith Catalan number. */ |
||
end /*i*/ |
|||
⚫ | |||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
Line 1,223: | Line 1,221: | ||
<lang rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
<lang rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
||
parse arg N . /*Obtain the optional argument from CL.*/ |
parse arg N . /*Obtain the optional argument from CL.*/ |
||
if N=='' | N==" |
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
||
numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/ |
numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/ |
||
do j=1 for N /* [↓] display N Catalan numbers. */ |
|||
say comb(j+j, j) % (j+1) /*display the Jth Catalan number. */ |
|||
end /*j*/ |
|||
end /*j*/ |
|||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
Line 1,241: | Line 1,238: | ||
<lang rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
<lang rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
||
parse arg N . /*Obtain the optional argument from CL.*/ |
parse arg N . /*Obtain the optional argument from CL.*/ |
||
if N=='' | N==" |
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
||
numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/ |
numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/ |
||
!.=. |
!.=. |
||
do j=1 for N /* [↓] display N Catalan numbers. */ |
|||
say comb(j+j, j) % (j+1) /*display the Jth Catalan number. */ |
|||
end /*j*/ |
end /*j*/ |
||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
Revision as of 21:09, 16 January 2017
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Print out the first 15 Catalan numbers by extracting them from Pascal's triangle.
- See
- Catalan Numbers and the Pascal Triangle. This method enables calculation of Catalan Numbers using only addition and subtraction.
- Catalan's Triangle for a Number Triangle that generates Catalan Numbers using only addition.
- Related Tasks
360 Assembly
For maximum compatibility, this program uses only the basic instruction set. <lang 360asm>CATALAN CSECT
USING CATALAN,R13,R12
SAVEAREA B STM-SAVEAREA(R15)
DC 17F'0' DC CL8'CATALAN'
STM STM R14,R12,12(R13)
ST R13,4(R15) ST R15,8(R13) LR R13,R15 LA R12,4095(R13) LA R12,1(R12)
- ---- CODE
LA R0,1 ST R0,T t(1)=1 LA R4,0 ix:i=1 LA R6,1 by 1 LH R7,N to n
LOOPI BXH R4,R6,ENDLOOPI loop i
LR R5,R4 ix:j=i+1 LA R5,2(R5) i+2 LA R8,0 BCTR R8,0 by -1 LA R9,1 to 2
LOOP1J BXLE R5,R8,ENLOOP1J loop j
LR R10,R5 j BCTR R10,0 SLA R10,2 L R2,T(R10) r2=t(j) LR R1,R10 j SH R1,=H'4' L R3,T(R1) r3=t(j-1) AR R2,R3 r2=r2+r3 ST R2,T(R10) t(j)=t(j)+t(j-1) B LOOP1J
ENLOOP1J EQU *
LR R1,R4 i BCTR R1,0 SLA R1,2 L R3,T(R1) t(i) LA R1,4(R1) ST R3,T(R1) t(i+1) LR R5,R4 ix:j=i+2 LA R5,3(R5) i+3 LA R8,0 BCTR R8,0 by -1 LA R9,1 to 2
LOOP2J BXLE R5,R8,ENLOOP2J loop j
LR R10,R5 j BCTR R10,0 SLA R10,2 L R2,T(R10) r2=t(j) LR R1,R10 j SH R1,=H'4' L R3,T(R1) r3=t(j-1) AR R2,R3 r2=r2+r3 ST R2,T(R10) t(j)=t(j)+t(j-1) B LOOP2J
ENLOOP2J EQU *
LR R1,R4 i BCTR R1,0 SLA R1,2 L R2,T(R1) t(i) LA R1,4(R1) L R3,T(R1) t(i+1) SR R3,R2 CVD R3,P UNPK Z,P MVC C,Z OI C+L'C-1,X'F0' MVC WTOBUF(8),C+8 WTO MF=(E,WTOMSG) B LOOPI
ENDLOOPI EQU *
- ---- END CODE
CNOP 0,4 L R13,4(0,R13) LM R14,R12,12(R13) XR R15,R15 BR R14
- ---- DATA
N DC H'15' T DC 17F'0' P DS PL8 Z DS ZL16 C DS CL16 WTOMSG DS 0F
DC H'80' DC H'0'
WTOBUF DC CL80' '
YREGS END</lang>
- Output:
00000001 00000002 00000005 00000014 00000042 00000132 00000429 00001430 00004862 00016796 00058786 00208012 00742900 02674440 09694845
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
ALGOL 68
<lang algol68>INT n = 15; [ 0 : n + 1 ]INT t; t[0] := 0; t[1] := 1; FOR i TO n DO
FOR j FROM i BY -1 TO 2 DO t[j] := t[j] + t[j-1] OD; t[i+1] := t[i]; FOR j FROM i+1 BY -1 TO 2 DO t[j] := t[j] + t[j-1] OD; print( ( whole( t[i+1] - t[i], 0 ), " " ) )
OD</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
APL
<lang apl>
⍝ Based heavily on the J solution CATALAN←{¯1↓↑-/1 ¯1↓¨(⊂⎕IO+0 0)⍉¨0 2⌽¨⊂(⎕IO-⍨⍳N){+\⍣⍺⊢⍵}⍤0 1⊢1⍴⍨N←⍵+2}
</lang>
- Output:
CATALAN 15 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
Batch File
<lang dos>@echo off setlocal ENABLEDELAYEDEXPANSION set n=15 set /A nn=n+1 for /L %%i in (0,1,%nn%) do set t.%%i=0 set t.1=1 for /L %%i in (1,1,%n%) do (
set /A ip=%%i+1 for /L %%j in (%%i,-1,1) do ( set /A jm=%%j-1
set /A t.%%j=t.%%j+t.!jm! )
set /A t.!ip!=t.%%i for /L %%j in (!ip!,-1,1) do ( set /A jm=%%j-1
set /A t.%%j=t.%%j+t.!jm! )
set /A ci=t.!ip!-t.%%i
echo !ci!
)
) pause</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
C
<lang c> //This code implements the print of 15 first Catalan's Numbers //Formula used: // __n__ // | | (n + k) / k n>0 // k=2
- include <stdio.h>
- include <stdlib.h>
//the number of Catalan's Numbers to be printed const int N = 15;
int main() {
//loop variables (in registers) register int k, n;
//necessarily ull for reach big values unsigned long long int num, den;
//the nmmber int catalan;
//the first is not calculated for the formula printf("1 ");
//iterating fro 2 to 15 for (n=2; n<=N; ++n) { //initializaing for products num = den = 1; //applying the formula for (k=2; k<=n; ++k) { num *= (n+k); den *= k; catalan = num /den; } //output printf("%d ", catalan); }
//the end printf("\n"); return 0;
} </lang>
- Output:
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
C#
<lang csharp> int n = 15; List<int> t = new List<int>() { 0, 1 }; for (int i = 1; i <= n; i++) {
for (var j = i; j > 1; j--) t[j] += t[j - 1]; t.Add(t[i]); for (var j = i + 1; j > 1; j--) t[j] += t[j - 1]; Console.Write(((i == 1) ? "" : ", ") + (t[i + 1] - t[i]));
} </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
EchoLisp
<lang scheme> (define dim 100) (define-syntax-rule (Tidx i j) (+ i (* dim j)))
- generates Catalan's triangle
- T (i , j) = T(i-1,j) + T (i, j-1)
(define (T n) (define i (modulo n dim)) (define j (quotient n dim)) (cond ((zero? i) 1) ;; left column = 1 ((= i j) (T (Tidx (1- i) j))) ;; diagonal value = left value (else (+ (T (Tidx (1- i) j)) (T (Tidx i (1- j)))))))
(remember 'T #(1)) </lang>
- Output:
<lang scheme>
- take elements on diagonal = Catalan numbers
(for ((i (in-range 0 16))) (write (T (Tidx i i))))
→ 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</lang>
Elixir
<lang elixir>defmodule Catalan do
def numbers(num) do {result,_} = Enum.reduce(1..num, {[],{0,1}}, fn i,{list,t0} -> t1 = numbers(i, t0) t2 = numbers(i+1, Tuple.insert_at(t1, i+1, elem(t1, i))) {[elem(t2, i+1) - elem(t2, i) | list], t2} end) Enum.reverse(result) end defp numbers(0, t), do: t defp numbers(n, t), do: numbers(n-1, put_elem(t, n, elem(t, n-1) + elem(t, n)))
end
IO.inspect Catalan.numbers(15)</lang>
- Output:
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
ERRE
<lang ERRE> PROGRAM CATALAN
!$DOUBLE
DIM CATALAN[50]
FUNCTION ODD(X)
ODD=FRC(X/2)<>0
END FUNCTION
PROCEDURE GETCATALAN(L)
LOCAL J,K,W LOCAL DIM PASTRI[100]
L=L*2 PASTRI[0]=1 J=0 WHILE J<L DO J+=1 K=INT((J+1)/2) PASTRI[K]=PASTRI[K-1] FOR W=K TO 1 STEP -1 DO PASTRI[W]+=PASTRI[W-1] END FOR IF NOT(ODD(J)) THEN K=INT(J/2) CATALAN[K]=PASTRI[K]-PASTRI[K-1] END IF END WHILE
END PROCEDURE
BEGIN
LL=15 GETCATALAN(LL) FOR I=1 TO LL DO WRITE("### ####################";I;CATALAN[I]) END FOR
END PROGRAM </lang>
- Output:
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
FreeBASIC
<lang freebasic>' version 15-09-2015 ' compile with: fbc -s console
- Define size 31 ' (N * 2 + 1)
Sub pascal_triangle(rows As Integer, Pas_tri() As ULongInt)
Dim As Integer x, y
For x = 1 To rows Pas_tri(1,x) = 1 Pas_tri(x,1) = 1 Next
For x = 2 To rows For y = 2 To rows + 1 - x Pas_tri(x, y) = pas_tri(x - 1 , y) + pas_tri(x, y - 1) Next Next
End Sub
' ------=< MAIN >=------
Dim As Integer count, row Dim As ULongInt triangle(1 To size, 1 To size)
pascal_triangle(size, triangle())
' 1 1 1 1 1 1 ' 1 2 3 4 5 6 ' 1 3 6 10 15 21 ' 1 4 10 20 35 56 ' 1 5 15 35 70 126 ' 1 6 21 56 126 252 ' The Pascal triangle is rotated 45 deg. ' to find the Catalan number we need to follow the diagonal ' for top left to bottom right ' take the number on diagonal and subtract the number in de cell ' one up and one to right ' 1 (2 - 1), 2 (6 - 4), 5 (20 - 15) ...
Print "The first 15 Catalan numbers are" : print
count = 1 : row = 2
Do
Print Using "###: #########"; count; triangle(row, row) - triangle(row +1, row -1) row = row + 1 count = count + 1
Loop Until count > 15
' empty keyboard buffer While InKey <> "" : Wend Print : Print "hit any key to end program" Sleep End</lang>
- Output:
The first 15 Catalan numbers are 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
Groovy
<lang Groovy> class Catalan {
public static void main(String[] args) { BigInteger N = 15; BigInteger k,n,num,den; BigInteger catalan; print(1); for(n=2;n<=N;n++) { num = 1; den = 1; for(k=2;k<=n;k++) { num = num*(n+k); den = den*k; catalan = num/den; } print(" " + catalan); } }
} </lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Haskell
As required by the task this implementation extracts the Catalan numbers from Pascal's triangle, rather than calculating them directly. Also, note that it (correctly) produces [1, 1] as the first two numbers. <lang haskell>import System.Environment (getArgs)
-- Pascal's triangle. pascal :: Integer pascal = [1] : map (\row -> 1 : zipWith (+) row (tail row) ++ [1]) pascal
-- The Catalan numbers from Pascal's triangle. This uses a method from -- http://www.cut-the-knot.org/arithmetic/algebra/CatalanInPascal.shtml -- (see "Grimaldi"). catalan :: [Integer] catalan = map (diff . uncurry drop) $ zip [0..] (alt pascal)
where alt (x:_:zs) = x : alt zs -- every other element of an infinite list diff (x:y:_) = x - y diff (x:_) = x
main :: IO () main = do
ns <- fmap (map read) getArgs :: IO [Int] mapM_ (print . flip take catalan) ns</lang>
- Output:
./catalan 15 [1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
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>
Java
<lang java>public class Test {
public static void main(String[] args) { int N = 15; int[] t = new int[N + 2]; t[1] = 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];
System.out.printf("%d ", t[i + 1] - t[i]); } }
}</lang>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
JavaScript
ES5
Iteration
<lang javascript>var n = 15; for (var t = [0, 1], i = 1; i <= n; i++) {
for (var j = i; j > 1; j--) t[j] += t[j - 1]; t[i + 1] = t[i]; for (var j = i + 1; j > 1; j--) t[j] += t[j - 1]; document.write(i == 1 ? : ', ', t[i + 1] - t[i]);
}</lang>
- Output:
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845
ES6
Functional composition
<lang JavaScript>(() => {
'use strict';
// CATALAN
// catalanSeries :: Int -> [Int] let catalanSeries = n => { let alternate = xs => xs.reduce( (a, x, i) => i % 2 === 0 ? a.concat([x]) : a, [] ), diff = xs => xs.length > 1 ? xs[0] - xs[1] : xs[0];
return alternate(pascal(n * 2)) .map((xs, i) => diff(drop(i, xs))); }
// PASCAL
// pascal :: Int -> Int let pascal = n => until( m => m.level <= 1, m => { let nxt = zipWith( (a, b) => a + b, [0].concat(m.row), m.row.concat(0) ); return { row: nxt, triangle: m.triangle.concat([nxt]), level: m.level - 1 } }, { level: n, row: [1], triangle: [ [1] ] } ) .triangle;
// GENERIC FUNCTIONS
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] let zipWith = (f, xs, ys) => xs.length === ys.length ? ( xs.map((x, i) => f(x, ys[i])) ) : undefined;
// until :: (a -> Bool) -> (a -> a) -> a -> a let until = (p, f, x) => { let v = x; while (!p(v)) v = f(v); return v; }
// drop :: Int -> [a] -> [a] let drop = (n, xs) => xs.slice(n);
// tail :: [a] -> [a] let tail = xs => xs.length ? xs.slice(1) : undefined;
return tail(catalanSeries(16));
})();</lang>
- Output:
<lang JavaScript>[1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845]</lang>
jq
The first identity (C(2n,n) - C(2n, n-1)) given in the reference is used in accordance with the task description, but it would of course be more efficient to factor out C(2n,n) and use the expression C(2n,n)/(n+1). See also Catalan_numbers#jq for other 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;
- Direct (naive) computation using two numbers in Pascal's triangle:
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>
Lua
For each line of odd-numbered length from Pascal's triangle, print the middle number minus the one immediately to its right. This solution is heavily based on the Lua code to generate Pascal's triangle from the page for that task. <lang Lua>function nextrow (t)
local ret = {} t[0], t[#t + 1] = 0, 0 for i = 1, #t do ret[i] = t[i - 1] + t[i] end return ret
end
function catalans (n)
local t, middle = {1} for i = 1, n do middle = math.ceil(#t / 2) io.write(t[middle] - (t[middle + 1] or 0) .. " ") t = nextrow(nextrow(t)) end
end
catalans(15)</lang>
- Output:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
Mathematica / Wolfram Language
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
Nim
<lang nim>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
Oforth
<lang Oforth>: pascal(n) [ 1 ] #[ dup 0 + 0 rot + zipWith(#+) ] times(n) ;
- catalan(n) pascal(n 2 * ) at(n 1+) n 1+ / ;</lang>
- Output:
>15 seq map(#catalan) . [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 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]
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
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
Phix
Calculates the minimum pascal triangle in minimum memory. Inspired by the comments in, but not the code of the FreeBasic example <lang Phix>constant N = 15 -- accurate to 30, nan/inf for anything over 514 (bigatom version is below). sequence catalan = {}, -- (>=1 only)
p = repeat(1,N+1)
atom p1 for i=1 to N do
p1 = p[1]*2 catalan = append(catalan,p1-p[2]) for j=1 to N-i+1 do p1 += p[j+1] p[j] = p1 end for
-- ?p[1..N-i+1] end for ?catalan</lang>
- Output:
{1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845}
Explanatory comments to accompany the above <lang Phix>-- FreeBASIC said: --' 1 1 1 1 1 1 --' 1 2 3 4 5 6 --' 1 3 6 10 15 21 --' 1 4 10 20 35 56 --' 1 5 15 35 70 126 --' 1 6 21 56 126 252 --' The Pascal triangle is rotated 45 deg. --' to find the Catalan number we need to follow the diagonal --' for top left to bottom right --' take the number on diagonal and subtract the number in de cell --' one up and one to right --' 1 (2 - 1), 2 (6 - 4), 5 (20 - 15) ... -- -- The first thing that struck me was it is twice as big as it needs to be, -- something like this would do... -- 1 1 1 1 1 1 -- 2 3 4 5 6 -- 6 10 15 21 -- 20 35 56 -- 70 126 -- 252 -- It is more obvious from the upper square that the diagonal on that, which is -- that same as column 1 on this, is twice the previous, which on the second -- diagram is in column 2. Further, once we have calculated the value for column -- one above, we can use it immediately to calculate the next catalan number and -- do not need to store it. Lastly we can overwrite row 1 with row 2 etc in situ, -- and the following shows what we need for subsequent rounds: -- 1 1 1 1 1 -- 3 4 5 6 -- 10 15 21 -- 35 56 -- 126 (unused)</lang> The following bigatom version is over ten times faster than the equivalent on Catalan_numbers <lang Phix>include builtins\bigatom.e
function catalanB(integer n) -- very very fast! sequence catalan = {},
p = repeat(1,n+1)
bigatom p1
if n=0 then return 1 end if for i=1 to n do p1 = ba_multiply(p[1],2) catalan = append(catalan,ba_sub(p1,p[2])) for j=1 to n-i+1 do p1 = ba_add(p1,p[j+1]) p[j] = p1 end for end for return catalan[n]
end function
atom t0 = time() string sc100 = ba_sprint(catalanB(100)) printf(1,"%d: %s (%3.2fs)\n",{100,sc100,time()-t0}) atom t0 = time() string sc250 = ba_sprint(catalanB(250)) printf(1,"%d: %s (%3.2fs)\n",{250,sc250,time()-t0})</lang>
- Output:
100: 896519947090131496687170070074100632420837521538745909320 (0.08s) 250: 465116795969233796497747947259667807407291160080922096111953326525143875193659257831340309862635877995262413955019878805418475969029457769094808256 (1.01s)
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
All of the REXX program examples can handle arbitrary large numbers. <lang rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ parse arg N . /*Obtain the optional argument from CL.*/ if N== | N=="," then N=15 /*Not specified? Then use the default.*/ numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/ @.=0; @.1=1 /*stem array default; define 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 all 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 and displays Catalan numbers from a Pascal's triangle. */ parse arg N . /*Obtain the optional argument from CL.*/ if N== | N=="," then N=15 /*Not specified? Then use the default.*/ numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/ @.=0; @.1=1 /*stem array default; define 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 all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ @: 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 and displays Catalan numbers from a Pascal's triangle. */ parse arg N . /*Obtain the optional argument from CL.*/ if N== | N=="," then N=15 /*Not specified? Then use the default.*/ numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/
do j=1 for N /* [↓] display N Catalan numbers. */ say comb(j+j, j) % (j+1) /*display the Jth Catalan number. */ end /*j*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ !: procedure; parse arg z; _=1; do j=1 for arg(1); _=_*j; end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ 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 coefficients, memoized
This REXX version uses memoization for the calculation of factorials. <lang rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ parse arg N . /*Obtain the optional argument from CL.*/ if N== | N=="," then N=15 /*Not specified? Then use the default.*/ numeric digits max(9, N%2 + N%8) /*so we can handle huge Catalan numbers*/ !.=.
do j=1 for N /* [↓] display N Catalan numbers. */ say comb(j+j, j) % (j+1) /*display the Jth Catalan number. */ end /*j*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ !: procedure expose !.; parse arg z; if !.z\==. then return !.z; _=1
do j=1 for arg(1); _=_*j; end; !.z=_; return _
/*──────────────────────────────────────────────────────────────────────────────────────*/ 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.
Ring
<lang ring> n=15 cat = list(n+2) cat[1]=1 for i=1 to n
for j=i+1 to 2 step -1 cat[j]=cat[j]+cat[j-1] next cat[i+1]=cat[i] for j=i+2 to 2 step -1 cat[j]=cat[j]+cat[j-1] next see "" + (cat[i+1]-cat[i]) + " "
next </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..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
p catalan(15)</lang>
- Output:
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
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
Scilab
<lang>n=15 t=zeros(1,n+2) t(1)=1 for i=1:n
for j=i+1:-1:2 t(j)=t(j)+t(j-1) end t(i+1)=t(i) for j=i+2:-1:2 t(j)=t(j)+t(j-1) end disp(t(i+1)-t(i))
end</lang>
- Output:
1. 2. 5. 14. 42. 132. 429. 1430. 4862. 16796. 58786. 208012. 742900. 2674440. 9694845.
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
Sidef
<lang ruby>func catalan(num) {
var t = [0, 1]; range(1, num).map { |i| range(i, 1, -1).each {|j| t[j] += t[j-1]}; t[i+1] = t[i]; range(i+1, 1, -1).each {|j| t[j] += t[j-1]}; t[i+1] - t[i]; }
} say catalan(15).join(' ');</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
smart BASIC
-- Scott A. Rossell, 12-26-16 <lang qbasic>PRINT "Catalan Numbers from Pascal's Triangle"!PRINT x = 15 DIM t(x+2) t(1) = 1 FOR n = 1 TO x
FOR m = n TO 1 STEP -1 t(m) = t(m) + t(m-1) NEXT m t(n+1) = t(n) FOR m = n+1 TO 1 STEP -1 t(m) = t(m) + t(m-1) NEXT m
PRINT n,"#######":t(n+1) - t(n) NEXT n</lang>
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
TI-83 BASIC
<lang ti83b>"CATALAN 15→N seq(0,I,1,N+2)→L1 1→L1(1) For(I,1,N) For(J,I+1,2,-1) L1(J)+L1(J-1)→L1(J) End L1(I)→L1(I+1) For(J,I+2,2,-1) L1(J)+L1(J-1)→L1(J) End Disp L1(I+1)-L1(I) End</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 Done
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>
Visual Basic
<lang vb> Sub catalan()
Const n = 15 Dim t(n + 2) As Long Dim i As Integer, j As Integer t(1) = 1 For i = 1 To n For j = i + 1 To 2 Step -1 t(j) = t(j) + t(j - 1) Next j t(i + 1) = t(i) For j = i + 2 To 2 Step -1 t(j) = t(j) + t(j - 1) Next j Debug.Print i, t(i + 1) - t(i) Next i
End Sub 'catalan </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)
ZX Spectrum Basic
<lang zxbasic>10 LET N=15 20 DIM t(N+2) 30 LET t(2)=1 40 FOR i=2 TO N+1 50 FOR j=i TO 2 STEP -1: LET t(j)=t(j)+t(j-1): NEXT j 60 LET t(i+1)=t(i) 70 FOR j=i+1 TO 2 STEP -1: LET t(j)=t(j)+t(j-1): NEXT j 80 PRINT t(i+1)-t(i);" "; 90 NEXT i</lang>
- Programming Tasks
- Solutions by Programming Task
- 360 Assembly
- Ada
- ALGOL 68
- APL
- AutoHotkey
- Batch File
- C
- C++
- C sharp
- D
- EchoLisp
- Elixir
- ERRE
- FreeBASIC
- Groovy
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Jq
- Lua
- Mathematica
- Wolfram Language
- MATLAB
- Octave
- Nim
- Oforth
- PARI/GP
- Pascal
- Perl
- Ntheory
- Perl 6
- Phix
- PicoLisp
- Python
- Racket
- REXX
- Ring
- Ruby
- Run BASIC
- Scilab
- Seed7
- Sidef
- Smart BASIC
- Tcl
- TI-83 BASIC
- VBScript
- Visual Basic
- Zkl
- ZX Spectrum Basic