CatalanNumbers.cs

/***
 * Computes the Catalan Numbers. A dynamic-programming solution.
 * 
 * Wikipedia: https://en.wikipedia.org/wiki/Catalan_number
 */

usingSystem.Diagnostics;
usingSystem.Collections.Generic;
usingSystem.Numerics;

namespaceAlgorithms.Numeric
{
publicstaticclassCatalanNumbers
{
/// <summary>
/// Internal cache.
/// By default contains the first two catalan numbers for the ranks: 0, and 1.
/// </summary>
privatestaticreadonlyDictionary<uint,BigInteger>CachedCatalanNumbers=newDictionary<uint,BigInteger>{{0,1},{1,1}};

/// <summary>
/// Helper method.
/// </summary>
/// <param name="rank"></param>
/// <returns></returns>
privatestaticBigInteger_recursiveHelper(uintrank)
{
if(CachedCatalanNumbers.ContainsKey(rank))
returnCachedCatalanNumbers[rank];

BigIntegernumber=0;
varlastRank=rank-1;

for(uinti=0;i<=lastRank;++i)
{
varfirstPart=_recursiveHelper(i);
varsecondPart=_recursiveHelper(lastRank-i);

if(!CachedCatalanNumbers.ContainsKey(i))CachedCatalanNumbers.Add(i,firstPart);
if(!CachedCatalanNumbers.ContainsKey(lastRank-i))CachedCatalanNumbers.Add(lastRank-i,secondPart);

number=number+(firstPart*secondPart);
}

returnnumber;
}

/// <summary>
/// Public API.
/// </summary>
/// <param name="rank"></param>
/// <returns></returns>
publicstaticBigIntegerGetNumber(uintrank)
{
// Assert the cache is not empty.
Debug.Assert(CachedCatalanNumbers.Count>=2);

return_recursiveHelper(rank);
}

/// <summary>
/// Calculate the number using the Binomial Coefficients algorithm
/// </summary>
/// <param name="rank"></param>
/// <returns></returns>
publicstaticBigIntegerGetNumberByBinomialCoefficients(uintrank)
{
// Calculate by binomial coefficient.
returnBinomialCoefficients.Calculate(rank);
}

/// <summary>
/// Return the list of catalan numbers between two ranks, inclusive
/// </summary>
/// <param name="fromRank"></param>
/// <param name="toRank"></param>
/// <returns></returns>
publicstaticList<BigInteger>GetRange(uintfromRank,uinttoRank)
{
varnumbers=newList<BigInteger>();

if(fromRank>toRank)
returnnull;

for(vari=fromRank;i<=toRank;++i)
numbers.Add(GetNumber(i));

returnnumbers;
}
}
}