Catalan numbers/Pascal's triangle: Difference between revisions

Content added Content deleted

Inline

Revision as of 22:55, 23 December 2013

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.

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

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] + t[j - 1];
       t[i + 1] = t[i];
       foreach_reverse (immutable j; 2 .. i + 2)
           t[j] = 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:

MATLAB / Octave

<lang MATLAB>p = pascal(17); diag(p(2:end-1,2:end-1))-diag(p,2)</lang> Output:

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:

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

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

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

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

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