lambdaway :: catalan

7 | list | login |load

| |

_h1 catalan numbers

_p Following [[https://rosettacode.org/wiki/Catalan_numbers|https://rosettacode.org/wiki/Catalan_numbers]], three methods to compute the Catalan numbers.

_h2 lambdatalk

_h3 1) catalan1
_img https://rosettacode.org/w/index.php?title=Special:MathShowImage&hash=0b0f02c997930b943155f4bc4cda87db&mode=mathml

{pre
'{def catalan1
 {def fac
  {lambda {:n}
   {* {S.serie 1 :n}}}}
 {lambda {:n}
  {if {= :n 0}
   then 1
   else {round
         {/ {fac {* 2 :n}}
            {fac {+ :n 1}}
            {fac :n}} }}}}
-> {def catalan1
 {def fac
  {lambda {:n}
   {* {S.serie 1 :n}}}}
 {lambda {:n}
  {if {= :n 0}
   then 1
   else {round {/ {fac {* 2 :n}}
                     {fac {+ :n 1}}
                     {fac :n}} }}}}

'{S.map catalan1 {S.serie 0 15}}
-> 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
}

_h3 2) catalan2

_img https://rosettacode.org/w/index.php?title=Special:MathShowImage&hash=9268109b2ac8f54b79f485fb7563cf5d&mode=mathml

{pre
'{def catalan2
 {def catalan2.sum
  {lambda {:n :a :s :i}
   {if {= :i :n}
    then {A.set! :n :s :a}
    else {catalan2.sum :n 
                       :a 
                       {+ :s {* {catalan2.loop :i :a}
                                {catalan2.loop {- :n :i 1} :a}}} 
                       {+ :i 1}} }}}
 {def catalan2.loop
  {lambda {:n :a}
   {if {= :n 0}
    then 1
    else {if {W.equal? {A.get :n :a} undefined}
    then {A.get :n {catalan2.sum :n :a 0 0}}
    else {A.get :n :a} }}}}
 {lambda {:n}
  {catalan2.loop :n {A.new}} }}
-> {def catalan2
 {def catalan2.sum
  {lambda {:n :a :s :i}
   {if {= :i :n}
    then {A.set! :n :s :a}
    else {catalan2.sum :n 
                    :a 
                    {+ :s {* {catalan2.loop :i :a}
                             {catalan2.loop {- :n :i 1} :a}}} 
                    {+ :i 1}} }}}
 {def catalan2.loop
  {lambda {:n :a}
   {if {= :n 0}
    then 1
    else {if {W.equal? {A.get :n :a} undefined}
    then {A.get :n {catalan2.sum :n :a 0 0}}
    else {A.get :n :a} }}}}
 {lambda {:n}
  {catalan2.loop :n {A.new}} }}

'{S.map catalan2 {S.serie 0 15}}
-> 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
}

_h3 3) catalan3

_img https://rosettacode.org/w/index.php?title=Special:MathShowImage&hash=519361c647c5c52d09f4b761f660c27c&mode=mathml

{pre
'{def catalan3
 {def catalan3.loop
  {lambda {:n :a}
   {if {= :n 0}
    then 1
    else {if {W.equal? {A.get :n :a} undefined}
    then {A.get :n
                {A.set! :n 
                        {/ {* {- {* 4 :n} 2}
                              {catalan3.loop {- :n 1} :a}}
                           {+ :n 1}}
                        :a}}
    else {A.get :n :a}
 }}}}
 {lambda {:n}
  {catalan3.loop :n {A.new}}}}
-> {def catalan3
 {def catalan3.loop
  {lambda {:n :a}
   {if {= :n 0}
    then 1
    else {if {W.equal? {A.get :n :a} undefined}
    then {A.get :n
                {A.set! :n 
                        {/ {* {- {* 4 :n} 2}
                              {catalan3.loop {- :n 1} :a}}
                           {+ :n 1}}
                        :a}}
    else {A.get :n :a}
 }}}}
 {lambda {:n}
  {catalan3.loop :n {A.new}}}}

'{S.map catalan3 {S.serie 0 15}}
-> 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
}

_h3 alternative

{pre
'{style 
 td { text-align:right;
      font-family:monospace; 
    }
}

'{table
 {tr {td} {td cat1} {td cat2} {td cat3}}
 {S.map {lambda {:i} {tr {td :i}
                         {td {catalan1 :i}}
                         {td {catalan2 :i}}
                         {td {catalan3 :i}}}} 
        {S.serie 0 15}} 
}
}

{table
 {tr {td} {td cat1} {td cat2} {td cat3}}
 {S.map {lambda {:i} {tr {td :i}
                         {td {catalan1 :i}}
                         {td {catalan2 :i}}
                         {td {catalan3 :i}}}} 
        {S.serie 0 15}} 
}

_h2 javascript

_h3 code

{pre °° 
var fc = [], c2 = [], c3 = [];

function fact(n) { 
  return fc[n] ? fc[n] : fc[n] = (n ? n * fact(n - 1) : 1); 
}

function cata1(n) { 
  return Math.floor(fact(2 * n) / fact(n + 1) / fact(n) + .5); 
}

function cata2(n) {
  if (n == 0) return 1;
  if (!c2[n]) {
    var s = 0;
    for (var i = 0; i < n; i++)
       s += cata2(i) * cata2(n - i - 1);
       c2[n] = s;
    }
  return c2[n];
}

function cata3(n) {
  if (n == 0) return 1;
  return c3[n] ? c3[n] : c3[n] = (4 * n - 2) * cata3(n - 1) / (n + 1);
}

function disp(x) {
  var e = document.createTextNode(x + '\n');
  document.getElementById('x').appendChild(e);
}

setTimeout( function() {
  disp("       meth1   meth2   meth3");
  for (var i = 0; i <= 15; i++)
    disp(i + '\t' + cata1(i) + '\t' + cata2(i) + '\t' + cata3(i));
  }, 1 )

°°}

_h3 output

{pre {@ id='output'}}

{script 
var fc = [], c2 = [], c3 = [];

function fact(n) { 
  return fc[n] ? fc[n] : fc[n] = (n ? n * fact(n - 1) : 1); 
}

function cata1(n) { 
  return Math.floor(fact(2 * n) / fact(n + 1) / fact(n) + .5); 
}

function cata2(n) {
  if (n == 0) return 1;
  if (!c2[n]) {
    var s = 0;
    for (var i = 0; i < n; i++)
       s += cata2(i) * cata2(n - i - 1);
       c2[n] = s;
    }
  return c2[n];
}

function cata3(n) {
  if (n == 0) return 1;
  return c3[n] ? c3[n] : c3[n] = (4 * n - 2) * cata3(n - 1) / (n + 1);
}

function disp(x) {
  var e = document.createTextNode(x + '\n');
  document.getElementById('output').appendChild(e);
}

setTimeout( function() {
  disp("       meth1   meth2   meth3");
  for (var i = 0; i <= 15; i++)
    disp(i + '\t' + cata1(i) + '\t' + cata2(i) + '\t' + cata3(i));
  }, 1 )

}

{style 
#page_content { background:#eee; }
pre { background:#fff; }
td { background:#ff8; text-align:right; font-family:monospace; }
}