Catalan numbers
| This page uses content from Wikipedia. The original article was at Catalan numbers. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
You are encouraged to solve this task according to the task description, using any language you may know.
Catalan numbers are a sequence of numbers which can be defined directly:
Or recursively:
Or alternatively (also recursive):
Implement at least one of these algorithms and print out the first 15 Catalan numbers with each. Memoization is not required, but would probably be worth the effort for most languages.
Ada
<lang Ada> with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Catalan is
function Catalan (N : Natural) return Natural is
Result : Positive := 1;
begin
for I in 1..N loop
Result := Result * 2 * (2 * I - 1) / (I + 1);
end loop;
return Result;
end Catalan;
begin
for N in 0..15 loop
Put_Line (Integer'Image (N) & " =" & Integer'Image (Catalan (N)));
end loop;
end Test_Catalan; </lang> Sample output:
0 = 1 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
Brat
<lang brat>catalan = { n |
true? n == 0
{ 1 }
{ (2 * ( 2 * n - 1) / ( n + 1 )) * catalan(n - 1) }
}
0.to 15 { n |
p "#{n} - #{catalan n}"
}</lang> Output:
0 - 1 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
C#
<lang csharp> using System; using System.Collections.Generic; using System.Linq; using System.Text;
namespace CatalanNumbers {
/// <summary>
/// Class that holds all options.
/// </summary>
public class CatalanNumberGenerator
{
private double Factorial(double n)
{
if (n == 0)
return 1;
return n * Factorial(n - 1);
}
public double FirstOption(double n)
{
double topMultiplier = 2;
return Factorial(topMultiplier * n)/(Factorial(n + 1)*Factorial(n));
}
public double SecondOption(double n)
{
if (n == 0)
{
return 1;
}
else
{
double sum = 0;
double i = 0;
for (; i <= (n - 1); i++)
{
sum += SecondOption(i) * SecondOption((n - 1) - i);
}
return sum;
}
}
public double ThirdOption(double n)
{
if (n == 0)
{
return 1;
}
else
{
return ((2 * (2 * n - 1)) / (n + 1)) * ThirdOption(n - 1);
}
}
}
}
// Program.cs using System; using System.Configuration; using System.Collections.Generic; using System.Linq; using System.Text;
// Main program // Be sure to add the following to the App.config file and add a reference to System.Configuration: // <?xml version="1.0" encoding="utf-8" ?> // <configuration> // <appSettings> // <clear/> // <add key="MaxCatalanNumber" value="50"/> // </appSettings> // </configuration> namespace CatalanNumbers {
class Program
{
static void Main(string[] args)
{
CatalanNumberGenerator generator = new CatalanNumberGenerator();
int i = 0;
DateTime initial;
DateTime final;
TimeSpan ts;
try
{
initial = DateTime.Now;
for (; i <= Convert.ToInt32(ConfigurationManager.AppSettings["MaxCatalanNumber"]); i++)
{
Console.WriteLine("CatalanNumber({0}):{1}", i, generator.FirstOption(i));
}
final = DateTime.Now;
ts = final - initial;
Console.WriteLine("It took {0}.{1} to execute\n", ts.Seconds, ts.Milliseconds);
i = 0;
initial = DateTime.Now;
for (; i <= Convert.ToInt32(ConfigurationManager.AppSettings["MaxCatalanNumber"]); i++)
{
Console.WriteLine("CatalanNumber({0}):{1}", i, generator.SecondOption(i));
}
final = DateTime.Now;
ts = final - initial;
Console.WriteLine("It took {0}.{1} to execute\n", ts.Seconds, ts.Milliseconds);
i = 0;
initial = DateTime.Now;
for (; i <= Convert.ToInt32(ConfigurationManager.AppSettings["MaxCatalanNumber"]); i++)
{
Console.WriteLine("CatalanNumber({0}):{1}", i, generator.ThirdOption(i));
}
final = DateTime.Now;
ts = final - initial;
Console.WriteLine("It took {0}.{1} to execute", ts.Seconds, ts.Milliseconds, ts.TotalMilliseconds);
Console.ReadLine();
}
catch (Exception ex)
{
Console.WriteLine("Stopped at index {0}:", i);
Console.WriteLine(ex.Message);
Console.ReadLine();
}
}
}
} </lang> Output:
CatalanNumber(0):1 CatalanNumber(1):1 CatalanNumber(2):2 CatalanNumber(3):5 CatalanNumber(4):14 CatalanNumber(5):42 CatalanNumber(6):132 CatalanNumber(7):429 CatalanNumber(8):1430 CatalanNumber(9):4862 CatalanNumber(10):16796 CatalanNumber(11):58786 CatalanNumber(12):208012 CatalanNumber(13):742900 CatalanNumber(14):2674440 CatalanNumber(15):9694845 It took 0.14 to execute CatalanNumber(0):1 CatalanNumber(1):1 CatalanNumber(2):2 CatalanNumber(3):5 CatalanNumber(4):14 CatalanNumber(5):42 CatalanNumber(6):132 CatalanNumber(7):429 CatalanNumber(8):1430 CatalanNumber(9):4862 CatalanNumber(10):16796 CatalanNumber(11):58786 CatalanNumber(12):208012 CatalanNumber(13):742900 CatalanNumber(14):2674440 CatalanNumber(15):9694845 It took 0.922 to execute CatalanNumber(0):1 CatalanNumber(1):1 CatalanNumber(2):2 CatalanNumber(3):5 CatalanNumber(4):14 CatalanNumber(5):42 CatalanNumber(6):132 CatalanNumber(7):429 CatalanNumber(8):1430 CatalanNumber(9):4862 CatalanNumber(10):16796 CatalanNumber(11):58786 CatalanNumber(12):208012 CatalanNumber(13):742900 CatalanNumber(14):2674440 CatalanNumber(15):9694845 It took 0.3 to execute
C
We declare 4 functions representing the four different algorithms for calculating Catalan numbers as given in the description of the task. (algorithms.h) <lang c>#if !defined __ALGORITHMS_H__
- define __ALGORITHMS_H__
unsigned long long calculateCatalanNumbersDirectFactorial(unsigned n); unsigned long long calculateCatalanNumbersDirectBinomialCoefficient(unsigned n); unsigned long long calculateCatalanNumbersRecursiveSum(unsigned n); unsigned long long calculateCatalanNumbersRecursiveFraction(unsigned n);
- endif //!defined __ALGORITHMS_H__</lang>
Here is the implementation of the algorithms. In addition, we define two supporting functions for the calculation of factorials and binomial coefficients. Because these two are only internal supporting code they are not declared in algorithm.h and thus are hidden from the outside world. (algorithms.c) <lang c>#include <math.h>
- include "algorithms.h"
unsigned long long calculateBinomialCoefficient(unsigned n, unsigned k); unsigned long long calculateFactorial(unsigned n);
unsigned long long calculateCatalanNumbersDirectFactorial(unsigned n)
{
if(n>1)
{
unsigned long long nFac = calculateFactorial(n);
return calculateFactorial(2 * n) / ((n + 1) * nFac * nFac);
}
else
{
return 1;
}
}
unsigned long long calculateCatalanNumbersDirectBinomialCoefficient(unsigned n)
{
if(n>1)
return 1.0 / (n + 1) * calculateBinomialCoefficient(2 * n, n);
else
return 1;
}
unsigned long long calculateCatalanNumbersRecursiveSum(unsigned n)
{
if(n>1)
{
const unsigned n_ = n - 1;
unsigned long long sum = 0;
unsigned i;
for(i = 0; i <= n_; i++)
sum += calculateCatalanNumbersRecursiveSum(i) * calculateCatalanNumbersRecursiveSum(n_ - i);
return sum;
}
else
{
return 1;
}
}
unsigned long long calculateCatalanNumbersRecursiveFraction(unsigned n)
{
if(n>1)
return (double)(2 * (2 * n - 1)) / (n + 1) * calculateCatalanNumbersRecursiveFraction(n-1);
else
return 1;
}
unsigned long long calculateFactorial(unsigned n)
{
if(n>1)
return n * calculateFactorial(n-1);
else
return 1;
}
unsigned long long calculateBinomialCoefficient(unsigned n, unsigned k)
{
double product = 1;
unsigned i;
if(k == 0) return 1; if(n == 0) return 0; for(i = 1; i <= k; i++) product *= ((double)(n - (k - i)) / i); return (unsigned long long)floor(product + 0.5); }</lang>
In order to test what we have done, a test function is declared. Usage of a function pointer parameter (note how the typedef simplifies the subsequent code) allows it to execute any or our algorithms. (tester.h) <lang c>#if !defined __TESTER_H__
- define __TESTER_H__
typedef unsigned long long (*Algorithm)(unsigned); void test(Algorithm, unsigned N, char* title);
- endif //!defined __TESTER_H__</lang>
Here is the implementation of our test function. (tester.c) <lang c>#include <stdio.h>
- include <string.h>
- include "tester.h"
void test(Algorithm algorithm, unsigned N, char* title)
{
unsigned i;
if(title != NULL && strlen(title) > 1)
printf("%s\n", title);
for(i = 0; i <= N; i++)
printf("C(%u)\t= %u\n", i, algorithm(i));
printf("\n");
}</lang>
Finally, we test the four different algorithms. Note that the first one (direct calculation using the factorial) only works up to N = 10 because some intermediate result (namely (2n)! with n = 11) exceeds the boundaries of an unsigned 64 bit integer. (catalanNumbersTest.c) <lang c>#include "tester.h"
- include "algorithms.h"
int main(int argc, char* argv[])
{
test(calculateCatalanNumbersDirectFactorial, 10, "Direct calculation using the factorial");
test(calculateCatalanNumbersDirectBinomialCoefficient, 15, "Direct calculation using a binomial coefficient");
test(calculateCatalanNumbersRecursiveSum, 15, "Recursive calculation using a sum");
test(calculateCatalanNumbersRecursiveFraction, 15, "Recursive calculation using a fraction");
return 0; }</lang>
Output (source code is compiled both by MS Visual C++ 10.0 (WinXP 32 bit) and GNU g++ 4.4.3 (Ubuntu 10.04 64 bit) compilers):
Direct calculation using the factorial C(0) = 1 C(1) = 1 C(2) = 2 C(3) = 5 C(4) = 14 C(5) = 42 C(6) = 132 C(7) = 429 C(8) = 1430 C(9) = 4862 C(10) = 16796 Direct calculation using a binomial coefficient C(0) = 1 C(1) = 1 C(2) = 2 C(3) = 5 C(4) = 14 C(5) = 42 C(6) = 132 C(7) = 429 C(8) = 1430 C(9) = 4862 C(10) = 16796 C(11) = 58786 C(12) = 208012 C(13) = 742900 C(14) = 2674440 C(15) = 9694845 Recursive calculation using a sum C(0) = 1 C(1) = 1 C(2) = 2 C(3) = 5 C(4) = 14 C(5) = 42 C(6) = 132 C(7) = 429 C(8) = 1430 C(9) = 4862 C(10) = 16796 C(11) = 58786 C(12) = 208012 C(13) = 742900 C(14) = 2674440 C(15) = 9694845 Recursive calculation using a fraction C(0) = 1 C(1) = 1 C(2) = 2 C(3) = 5 C(4) = 14 C(5) = 42 C(6) = 132 C(7) = 429 C(8) = 1430 C(9) = 4862 C(10) = 16796 C(11) = 58786 C(12) = 208012 C(13) = 742900 C(14) = 2674440 C(15) = 9694845
C++
We declare 4 classes representing the four different algorithms for calculating Catalan numbers as given in the description of the task. In addition, we declare two supporting classes for the calculation of factorials and binomial coefficients. Because these two are only internal supporting code they are hidden in namespace 'detail'. Overloading the function call operator to execute the calculation is an obvious decision when using C++. (algorithms.h) <lang cpp>#if !defined __ALGORITHMS_H__
- define __ALGORITHMS_H__
namespace rosetta
{
namespace catalanNumbers
{
namespace detail
{
class Factorial
{
public:
unsigned long long operator()(unsigned n)const;
};
class BinomialCoefficient
{
public:
unsigned long long operator()(unsigned n, unsigned k)const;
};
} //namespace detail
class CatalanNumbersDirectFactorial
{
public:
CatalanNumbersDirectFactorial();
unsigned long long operator()(unsigned n)const;
private:
detail::Factorial factorial;
};
class CatalanNumbersDirectBinomialCoefficient
{
public:
CatalanNumbersDirectBinomialCoefficient();
unsigned long long operator()(unsigned n)const;
private:
detail::BinomialCoefficient binomialCoefficient;
};
class CatalanNumbersRecursiveSum
{
public:
CatalanNumbersRecursiveSum();
unsigned long long operator()(unsigned n)const;
};
class CatalanNumbersRecursiveFraction
{
public:
CatalanNumbersRecursiveFraction();
unsigned long long operator()(unsigned n)const;
};
} //namespace catalanNumbers } //namespace rosetta
- endif //!defined __ALGORITHMS_H__</lang>
Here is the implementation of the algorithms. The c'tor of each class tells us the algorithm which will be used. (algorithms.cpp) <lang cpp>#include <iostream> using std::cout; using std::endl;
- include <cmath>
using std::floor;
- include "algorithms.h"
using namespace rosetta::catalanNumbers;
CatalanNumbersDirectFactorial::CatalanNumbersDirectFactorial()
{
cout<<"Direct calculation using the factorial"<<endl;
}
unsigned long long CatalanNumbersDirectFactorial::operator()(unsigned n)const
{
if(n>1)
{
unsigned long long nFac = factorial(n);
return factorial(2 * n) / ((n + 1) * nFac * nFac);
}
else
{
return 1;
}
}
CatalanNumbersDirectBinomialCoefficient::CatalanNumbersDirectBinomialCoefficient()
{
cout<<"Direct calculation using a binomial coefficient"<<endl;
}
unsigned long long CatalanNumbersDirectBinomialCoefficient::operator()(unsigned n)const
{
if(n>1)
return double(1) / (n + 1) * binomialCoefficient(2 * n, n);
else
return 1;
}
CatalanNumbersRecursiveSum::CatalanNumbersRecursiveSum()
{
cout<<"Recursive calculation using a sum"<<endl;
}
unsigned long long CatalanNumbersRecursiveSum::operator()(unsigned n)const
{
if(n>1)
{
const unsigned n_ = n - 1;
unsigned long long sum = 0;
for(unsigned i = 0; i <= n_; i++)
sum += operator()(i) * operator()(n_ - i);
return sum;
}
else
{
return 1;
}
}
CatalanNumbersRecursiveFraction::CatalanNumbersRecursiveFraction()
{
cout<<"Recursive calculation using a fraction"<<endl;
}
unsigned long long CatalanNumbersRecursiveFraction::operator()(unsigned n)const
{
if(n>1)
return (double(2 * (2 * n - 1)) / (n + 1)) * operator()(n-1);
else
return 1;
}
unsigned long long detail::Factorial::operator()(unsigned n)const
{
if(n>1)
return n * operator()(n-1);
else
return 1;
}
unsigned long long detail::BinomialCoefficient::operator()(unsigned n, unsigned k)const
{
if(k == 0)
return 1;
if(n == 0)
return 0;
double product = 1; for(unsigned i = 1; i <= k; i++) product *= (double(n - (k - i)) / i); return (unsigned long long)(floor(product + 0.5)); }</lang>
In order to test what we have done, a class Test is created. Using the template parameters N (number of Catalan numbers to be calculated) and A (the kind of algorithm to be used) the compiler will create code for all the test cases we need. What would C++ be without templates ;-) (tester.h) <lang cpp>#if !defined __TESTER_H__
- define __TESTER_H__
- include <iostream>
namespace rosetta
{
namespace catalanNumbers
{
template <int N, typename A>
class Test
{
public:
static void Do()
{
A algorithm;
for(int i = 0; i <= N; i++)
std::cout<<"C("<<i<<")\t= "<<algorithm(i)<<std::endl;
}
};
} //namespace catalanNumbers } //namespace rosetta
- endif //!defined __TESTER_H__</lang>
Finally, we test the four different algorithms. Note that the first one (direct calculation using the factorial) only works up to N = 10 because some intermediate result (namely (2n)! with n = 11) exceeds the boundaries of an unsigned 64 bit integer. (catalanNumbersTest.cpp) <lang cpp>#include "algorithms.h"
- include "tester.h"
using namespace rosetta::catalanNumbers;
int main(int argc, char* argv[])
{
Test<10, CatalanNumbersDirectFactorial>::Do();
Test<15, CatalanNumbersDirectBinomialCoefficient>::Do();
Test<15, CatalanNumbersRecursiveFraction>::Do();
Test<15, CatalanNumbersRecursiveSum>::Do();
return 0;
}</lang>
Output (source code is compiled both by MS Visual C++ 10.0 (WinXP 32 bit) and GNU g++ 4.4.3 (Ubuntu 10.04 64 bit) compilers):
Direct calculation using the factorial C(0) = 1 C(1) = 1 C(2) = 2 C(3) = 5 C(4) = 14 C(5) = 42 C(6) = 132 C(7) = 429 C(8) = 1430 C(9) = 4862 C(10) = 16796 Direct calculation using a binomial coefficient C(0) = 1 C(1) = 1 C(2) = 2 C(3) = 5 C(4) = 14 C(5) = 42 C(6) = 132 C(7) = 428 C(8) = 1430 C(9) = 4862 C(10) = 16796 C(11) = 58786 C(12) = 208012 C(13) = 742900 C(14) = 2674440 C(15) = 9694845 Recursive calculation using a fraction C(0) = 1 C(1) = 1 C(2) = 2 C(3) = 5 C(4) = 14 C(5) = 42 C(6) = 132 C(7) = 429 C(8) = 1430 C(9) = 4862 C(10) = 16796 C(11) = 58786 C(12) = 208012 C(13) = 742900 C(14) = 2674440 C(15) = 9694845 Recursive calculation using a sum C(0) = 1 C(1) = 1 C(2) = 2 C(3) = 5 C(4) = 14 C(5) = 42 C(6) = 132 C(7) = 429 C(8) = 1430 C(9) = 4862 C(10) = 16796 C(11) = 58786 C(12) = 208012 C(13) = 742900 C(14) = 2674440 C(15) = 9694845
Clojure
<lang Clojure>(def ! (memoize #(apply * (range 1 (inc %)))))
(defn catalan-numbers-direct []
(map #(/ (! (* 2 %))
(* (! (inc %)) (! %))) (range)))
(def catalan-numbers-recursive
#(->> [1 1] ; [c0 n1]
(iterate (fn c n [(* 2 (dec (* 2 n)) (/ (inc n)) c) (inc n)]) ,) (map first ,)))
user> (take 15 (catalan-numbers-direct)) (1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)
user> (take 15 (catalan-numbers-recursive)) (1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)</lang>
D
<lang d>import std.stdio, std.traits, std.bigint, std.typecons;
auto memoize(alias F)(ParameterTypeTuple!F n) {
alias ReturnType!F R;
static R[Tuple!(ParameterTypeTuple!F)] cache;
auto value = tuple(n) in cache;
if (value is null)
return cache[tuple(n)] = F(n);
else
return *value;
}
BigInt factorial(uint n) {
// auto return type doesn't work here because memoize!fact // has to know its return type at this point alias memoize!factorial mfact; return (n == 0) ? BigInt(1) : mfact(n - 1) * n;
}
auto catalanDirect(uint n) {
return factorial(2 * n) / (factorial(n + 1) * factorial(n));
}
BigInt catalan1(uint n) {
alias memoize!catalan1 mcat1;
if (n == 0)
return BigInt(1);
auto sum = BigInt(0);
foreach (i; 0 .. n)
sum += mcat1(i) * mcat1(n - 1 - i);
return sum;
}
BigInt catalan2(uint n) {
alias memoize!catalan2 mcat2;
if (n == 0)
return BigInt(1);
else
return (4*n - 2) * mcat2(n - 1) / (n + 1);
}
void main() {
foreach (i; 0 .. 15)
writefln("%2d => %10s %10s %10s", i,
toDecimalString(catalanDirect(i)),
toDecimalString(catalan1(i)),
toDecimalString(catalan2(i)));
}</lang> Output:
0 => 1 1 1 1 => 1 1 1 2 => 2 2 2 3 => 5 5 5 4 => 14 14 14 5 => 42 42 42 6 => 132 132 132 7 => 429 429 429 8 => 1430 1430 1430 9 => 4862 4862 4862 10 => 16796 16796 16796 11 => 58786 58786 58786 12 => 208012 208012 208012 13 => 742900 742900 742900 14 => 2674440 2674440 2674440
Fantom
<lang fantom> class Main {
static Int factorial (Int n)
{
Int res := 1
if (n>1)
(2..n).each |i| { res *= i }
return res
}
static Int catalanA (Int n)
{
return factorial(2*n)/(factorial(n+1) * factorial(n))
}
static Int catalanB (Int n)
{
if (n == 0)
{
return 1
}
else
{
sum := 0
n.times |i| { sum += catalanB(i) * catalanB(n-1-i) }
return sum
}
}
static Int catalanC (Int n)
{
if (n == 0)
{
return 1
}
else
{
return catalanC(n-1)*2*(2*n-1)/(n+1)
}
}
public static Void main ()
{
(1..15).each |n|
{
echo (n.toStr.padl(4) +
catalanA(n).toStr.padl(10) +
catalanB(n).toStr.padl(10) +
catalanC(n).toStr.padl(10))
}
}
} </lang>
22! exceeds the range of Fantom's Int class, so the first technique fails afer n=10
1 1 1 1 2 2 2 2 3 5 5 5 4 14 14 14 5 42 42 42 6 132 132 132 7 429 429 429 8 1430 1430 1430 9 4862 4862 4862 10 16796 16796 16796 11 -65 58786 58786 12 -2 208012 208012 13 0 742900 742900 14 97 2674440 2674440 15 -2 9694845 9694845
Forth
<lang forth>: catalan ( n -- ) 1 swap 1+ 1 do dup cr . i 2* 1- 2* i 1+ */ loop drop ;</lang>
Frink
Frink includes efficient algorithms for calculating arbitrarily-large binomial coefficients and memoizing factorials. <lang frink> catalan[n] := binomial[2n,n]/(n+1) for n = 0 to 15
println[catalan[n]]
</lang>
Go
Direct: <lang go>package main
import (
"big" "fmt"
)
func main() {
var b, c big.Int
for n := int64(0); n < 15; n++ {
fmt.Println(c.Div(b.Binomial(n*2, n), c.SetInt64(n+1)))
}
}</lang> Output:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
Haskell
<lang haskell>-- Three infinite lists, corresponding to the three definitions in the problem -- statement.
cats1 = map (\n -> product [n+2..2*n] `div` product [1..n]) [0..]
cats2 = 1 : map (\n -> sum $ zipWith (*) (reverse (take n cats2)) cats2) [1..]
cats3 = 1 : zipWith (\c n -> c*2*(2*n-1) `div` (n+1)) cats3 [1..]
main = mapM_ (print . take 15) [cats1, cats2, cats3]</lang> Output:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440] [1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440] [1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
Icon and Unicon
<lang Icon>procedure main(arglist) every writes(catalan(i)," ") end
procedure catalan(n) # return catalan(n) or fail static M initial M := table()
if n > 0 then
return (n = 1) | \M[n] | ( M[n] := (2*(2*n-1)*catalan(n-1))/(n+1))
end</lang>
Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
J
<lang j> ((! +:) % >:) i.15x 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</lang>
Java
Accuracy may be lost for larger n's due to floating-point arithmetic (seen for C(15) here). This implementation is memoized (factorial and Catalan numbers are stored in the Maps "facts", "catsI", "catsR1", and "catsR2"). <lang java5>import java.util.HashMap; import java.util.Map;
public class Catalan { private static final Map<Long, Double> facts = new HashMap<Long, Double>(); private static final Map<Long, Double> catsI = new HashMap<Long, Double>(); private static final Map<Long, Double> catsR1 = new HashMap<Long, Double>(); private static final Map<Long, Double> catsR2 = new HashMap<Long, Double>();
static{//pre-load the memoization maps with some answers facts.put(0L, 1D); facts.put(1L, 1D); facts.put(2L, 2D);
catsI.put(0L, 1D); catsR1.put(0L, 1D); catsR2.put(0L, 1D); }
private static double fact(long n){ if(facts.containsKey(n)){ return facts.get(n); } double fact = 1; for(long i = 2; i <= n; i++){ fact *= i; //could be further optimized, but it would probably be ugly } facts.put(n, fact); return fact; }
private static double catI(long n){ if(!catsI.containsKey(n)){ catsI.put(n, fact(2 * n)/(fact(n+1)*fact(n))); } return catsI.get(n); }
private static double catR1(long n){ if(catsR1.containsKey(n)){ return catsR1.get(n); } double sum = 0; for(int i = 0; i < n; i++){ sum += catR1(i) * catR1(n - 1 - i); } catsR1.put(n, sum); return sum; }
private static double catR2(long n){ if(!catsR2.containsKey(n)){ catsR2.put(n, ((2.0*(2*(n-1) + 1))/(n + 1)) * catR2(n-1)); } return catsR2.get(n); }
public static void main(String[] args){ for(int i = 0; i <= 15; i++){ System.out.println(catI(i)); System.out.println(catR1(i)); System.out.println(catR2(i)); } } } </lang> Output:
1.0 1.0 1.0 1.0 1.0 1.0 2.0 2.0 2.0 5.0 5.0 5.0 14.0 14.0 14.0 42.0 42.0 42.0 132.0 132.0 132.0 429.0 429.0 429.0 1430.0 1430.0 1430.0 4862.0 4862.0 4862.0 16796.0 16796.0 16796.0 58786.0 58786.0 58786.0 208012.0 208012.0 208012.0 742900.0 742900.0 742900.0 2674439.9999999995 2674440.0 2674440.0 9694844.999999998 9694845.0 9694845.0
MATLAB
<lang MATLAB>function n = catalanNumbers(n)
for i = (1:length(n))
n(i) = (1/(n(i)+1))*nchoosek(2*n(i),n(i));
end
end</lang> Sample Output: <lang MATLAB>>> catalanNumbers(14)
ans =
2674440
>> catalanNumbers((0:17))'
ans =
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845
35357670
129644790</lang>
PARI/GP
Memoization is not worthwhile; PARI has fast built-in facilities for calculating binomial coefficients and factorials. <lang parigp>Catalan(n)=binomial(2*n,n+1)/n</lang>
A second version: <lang parigp>Catalan(n)=(2*n)!/(n+1)!/n!</lang>
Naive version: <lang parigp>Catalan(n)=prod(k=n+2,2*n,k)/prod(k=2,n,k)</lang>
The first version takes about 1.5 seconds to compute the millionth Catalan number, while the second takes 3.9 seconds. The naive implementation, for comparison, takes 21 minutes (850 times longer). In any case, printing the first 15 is simple: <lang parigp>vector(15,n,Catalan(n))</lang>
Perl 6
<lang perl6>my @catalan := 1, gather for 0..* -> $n {
take (4*$n + 2) / ($n + 2) * @catalan[$n];
}
.say for @catalan[^15];</lang>
Output:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
PHP
<lang php> <?php
class CatalanNumbersSerie {
private static $cache = array(0 => 1);
private function fill_cache($i)
{
$accum = 0;
$n = $i-1;
for($k = 0; $k <= $n; $k++)
{
$accum += $this->item($k)*$this->item($n-$k);
}
self::$cache[$i] = $accum;
}
function item($i)
{
if (!isset(self::$cache[$i]))
{
$this->fill_cache($i);
}
return self::$cache[$i];
}
}
$cn = new CatalanNumbersSerie(); for($i = 0; $i <= 15;$i++) {
$r = $cn->item($i); echo "$i = $r\r\n";
} ?> </lang>
Output:
0 = 1 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
PicoLisp
<lang PicoLisp># Factorial (de fact (N)
(if (=0 N)
1
(* N (fact (dec N))) ) )
- Directly
(de catalanDir (N)
(/ (fact (* 2 N)) (fact (inc N)) (fact N)) )
- Recursively
(de catalanRec (N)
(if (=0 N)
1
(cache '*CatalalRec (format (seed N)) # Memoize
(sum
'((I) (* (catalanRec I) (catalanRec (- N I 1))))
(range 0 (dec N)) ) ) ) )
- Alternatively
(de catalanAlt (N)
(if (=0 N)
1
(*/ 2 (dec (* 2 N)) (catalanAlt (dec N)) (inc N)) ) )
- Test
(for (N 0 (> 15 N) (inc N))
(tab (2 4 8 8 8)
N
" => "
(catalanDir N)
(catalanRec N)
(catalanAlt N) ) )</lang>
Output:
0 => 1 1 1 1 => 1 1 1 2 => 2 2 2 3 => 5 5 5 4 => 14 14 14 5 => 42 42 42 6 => 132 132 132 7 => 429 429 429 8 => 1430 1430 1430 9 => 4862 4862 4862 10 => 16796 16796 16796 11 => 58786 58786 58786 12 => 208012 208012 208012 13 => 742900 742900 742900 14 => 2674440 2674440 2674440
Prolog
Works with SWI-Prolog. <lang Prolog>catalan(N) :- length(L1, N), L = [1 | L1], init(1,1,L1), numlist(0, N, NL), maplist(my_write, NL, L).
init(_, _, []).
init(V, N, [H | T]) :- N1 is N+1, H is 2 * (2 * N - 1) * V / N1, init(H, N1, T).
my_write(N, V) :- format('~w : ~w~n', [N, V]). </lang> Output :
?- catalan(15). 0 : 1 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 true .
Python
Three algorithms including explicit memoization. (Pythons factorial built-in function is not memoized internally).
Python will transparently switch to bignum-type integer arithmetic, so the code below works unchanged on computing larger catalan numbers such as cat(50) and beyond. <lang python>from math import factorial import functools
def memoize(func):
func.__cache = {}
def memoized(key):
# Returned, new, memoized version of decorated function
cache = func.__cache
if key in cache:
return cache[key]
else:
cache[key] = result = func(key)
return result
return functools.update_wrapper(memoized, func)
@memoize
def fact(n):
return factorial(n)
def cat_direct(n):
return fact(2*n) // fact(n + 1) // fact(n)
@memoize def catR1(n):
return ( 1 if n == 0
else sum( catR1(i) * catR1(n - 1 - i)
for i in range(n) ) )
@memoize def catR2(n):
return ( 1 if n == 0
else ( ( 4 * n - 2 ) * catR2( n - 1) ) // ( n + 1 ) )
if __name__ == '__main__':
def pr(results):
fmt = '%-10s %-10s %-10s'
print ((fmt % tuple(c.__name__ for c in defs)).upper())
print (fmt % tuple(['='*10]*3))
for r in zip(*results):
print (fmt % r)
defs = (cat_direct, catR1, catR2) results = [ tuple(c(i) for i in range(15)) for c in defs ] pr(results)</lang>
Sample Output
CAT_DIRECT CATR1 CATR2 ========== ========== ========== 1 1 1 1 1 1 2 2 2 5 5 5 14 14 14 42 42 42 132 132 132 429 429 429 1430 1430 1430 4862 4862 4862 16796 16796 16796 58786 58786 58786 208012 208012 208012 742900 742900 742900 2674440 2674440 2674440
Ruby
Using a memoization module found at the Ruby Application Archive.
<lang ruby># direct
def factorial(n)
(1..n).reduce(1, :*)
end
def catalan_direct(n)
factorial(2*n) / (factorial(n+1) * factorial(n))
end
- recursive
def catalan_rec1(n)
return 1 if n == 0
(0..n-1).inject(0) {|sum, i| sum + catalan_rec1(i) * catalan_rec1(n-1-i)}
end
def catalan_rec2(n)
return 1 if n == 0 2*(2*n - 1) * catalan_rec2(n-1) /(n+1)
end
- performance and results
require 'benchmark' require 'memoize' include Memoize
Benchmark.bm(10) do |b|
b.report('forget') {
16.times {|n| [n, catalan_direct(n), catalan_rec1(n), catalan_rec2(n)]}
}
b.report('memoized') {
memoize :factorial
memoize :catalan_direct
memoize :catalan_rec1
memoize :catalan_rec2
16.times {|n| [n, catalan_direct(n), catalan_rec1(n), catalan_rec2(n)]}
}
end
16.times {|n| p [n, catalan_direct(n), catalan_rec1(n), catalan_rec2(n)]}</lang>
The output shows the dramatic difference memoizing makes.
user system total real forget 11.578000 0.000000 11.578000 ( 11.687000) memoized 0.000000 0.000000 0.000000 ( 0.000000) [0, 1, 1, 1] [1, 1, 1, 1] [2, 2, 2, 2] [3, 5, 5, 5] [4, 14, 14, 14] [5, 42, 42, 42] [6, 132, 132, 132] [7, 429, 429, 429] [8, 1430, 1430, 1430] [9, 4862, 4862, 4862] [10, 16796, 16796, 16796] [11, 58786, 58786, 58786] [12, 208012, 208012, 208012] [13, 742900, 742900, 742900] [14, 2674440, 2674440, 2674440] [15, 9694845, 9694845, 9694845]
Tcl
<lang tcl>package require Tcl 8.5
- Memoization wrapper
proc memoize {function value generator} {
variable memoize
set key $function,$value
if {![info exists memoize($key)]} {
set memoize($key) [uplevel 1 $generator]
} return $memoize($key)
}
- The simplest recursive definition
proc tcl::mathfunc::catalan n {
if {[incr n 0] < 0} {error "must not be negative"}
memoize catalan $n {expr {
$n == 0 ? 1 : 2 * (2*$n - 1) * catalan($n - 1) / ($n + 1)
}}
}</lang> Demonstration: <lang tcl>for {set i 0} {$i < 15} {incr i} {
puts "C_$i = [expr {catalan($i)}]"
}</lang> Output:
C_0 = 1 C_1 = 1 C_2 = 2 C_3 = 5 C_4 = 14 C_5 = 42 C_6 = 132 C_7 = 429 C_8 = 1430 C_9 = 4862 C_10 = 16796 C_11 = 58786 C_12 = 208012 C_13 = 742900 C_14 = 2674440
Of course, this code also works unchanged (apart from extending the loop) for producing higher Catalan numbers. For example, here is the end of the output when asked to produce the first fifty:
C_45 = 2257117854077248073253720 C_46 = 8740328711533173390046320 C_47 = 33868773757191046886429490 C_48 = 131327898242169365477991900 C_49 = 509552245179617138054608572
Ursala
<lang ursala>#import std
- import nat
catalan = quotient^\successor choose^/double ~&
- cast %nL
t = catalan* iota 16</lang> output:
< 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845>