Catalan numbers/Pascal's triangle: Difference between revisions

From Rosetta Code
Content added Content deleted
(Updated D entry)
Line 4: Line 4:
=={{header|Ada}}==
=={{header|Ada}}==


Uses package Pascal from the Pascal triangle solution[[http://rosettacode.org/wiki/Pascal%27s_triangle#Ada]]
⚫
<lang Ada>with Ada.Text_IO;

⚫
<lang Ada>with Ada.Text_IO, Pascal;


procedure Catalan is
procedure Catalan is
Last: Positive := 17;
type Pos_Arr is array(Positive range <>) of Positive;
Row: Pascal.Row := Pascal.First_Row(2*Last+1);
function Pascal(R: Positive) return Pos_Arr is -- Pascal triangle, R'th row
A: Pos_Arr(1 .. R);
begin
for Row in 1 .. R loop
A(Row) := 1;
for J in reverse 2 .. Row-1 loop
A(J) := A(J) + A(J-1);
end loop;
end loop;
return A;
end Pascal;
begin
begin
for I in 1 .. 15 loop
for I in 1 .. Last loop
Row := Pascal.Next_Row(Row);
declare
Pas: Pos_Arr := Pascal(2*I+1); -- row 2*I+1 of Pascal triangle
Row := Pascal.Next_Row(Row);
⚫
Ada.Text_IO.Put(Integer'Image(Row(I+1)-Row(I+2)));
begin
⚫
Ada.Text_IO.Put(Integer'Image(Pas(I+1)-Pas(I+2)));
end;
end loop;
end loop;
end Catalan;</lang>
end Catalan;</lang>


{{out}}

<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790</pre>


=={{header|AutoHotkey}}==
=={{header|AutoHotkey}}==

Revision as of 15:17, 7 April 2014

Task
Catalan numbers/Pascal's triangle
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 := 17;   
  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 35357670 129644790

AutoHotkey

Works with: AutoHotkey_L

<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 //

  1. 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

Translation of: C++

<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
->


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

Perl

Translation of: C++

<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

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

Python

Translation of: C++

<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>

Works with: Python version 2.7

<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>

  1. 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

<lang rexx>/*REXX program obtains Catalan numbers from Pascal's triangle. */ numeric digits 200 /*might have large Catalan nums. */ parse arg N .; if N== then N=15 /*Any args? No, then use default*/ @.=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
 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

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

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
Retrieved from "https://rosettacode.org/wiki/Catalan_numbers/Pascal%27s_triangle?oldid=230141"