How to resolve the algorithm Catalan numbers step by step in the JavaScript programming language

Published on 12 May 2024 09:40 PM
#Javascript

How to resolve the algorithm Catalan numbers step by step in the JavaScript programming language

Table of Contents

Problem Statement

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 may be worth the effort when using the second method above.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Catalan numbers step by step in the JavaScript programming language

Explanation of the JavaScript Source Code:

Part 1 (Imperative Approach):

  • It defines three functions to calculate Catalan numbers:

    • cata1(n): Calculates using a formula.
    • cata2(n): Calculates using recursion with memoization.
    • cata3(n): Calculates using another recursive formula with memoization.

  • It prints the results for n from 0 to 15 using the three methods side by side for comparison.

Part 2 (Declarative Haskell-Inspired Approach):

  • catalansDefinitionThree: Generates an infinite sequence of Catalan numbers using a Haskell-inspired approach.
  • main: Takes the first 15 elements from the infinite sequence generated by catalansDefinitionThree.

Generic Utility Functions:

  • enumFrom(n): Generates an infinite sequence of integers starting from n.
  • pred(x): Decrements an integer by 1.
  • scanlGen(f)(startValue)(gen): Performs a scan left operation over an infinite list using a specified function and start value.
  • succ(x): Increments an integer by 1.
  • take(n)(xs): Takes the first n elements from a list.

Output:

The code generates the first 15 Catalan numbers and prints them to the console:

      meth1   meth2   meth3
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

Source code in the javascript programming language

<html><head><title>Catalan</title></head>
<body><pre id='x'></pre><script type="application/javascript">
function disp(x) {
	var e = document.createTextNode(x + '\n');
	document.getElementById('x').appendChild(e);
}

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);
}

disp("       meth1   meth2   meth3");
for (var i = 0; i <= 15; i++)
	disp(i + '\t' + cata1(i) + '\t' + cata2(i) + '\t' + cata3(i));

</script></body></html>


(() => {
    "use strict";

    // ----------------- CATALAN NUMBERS -----------------

    // catalansDefinitionThree :: [Int]
    const catalansDefinitionThree = () =>
        // An infinite sequence of Catalan numbers.
        scanlGen(
            c => n => Math.floor(
                (2 * c * pred(2 * n)) / succ(n)
            )
        )(1)(
            enumFrom(1)
        );


    // ---------------------- TEST -----------------------
    // main :: IO ()
    const main = () =>
        take(15)(
            catalansDefinitionThree()
        );


    // --------------------- GENERIC ---------------------

    // enumFrom :: Enum a => a -> [a]
    const enumFrom = function* (n) {
        // An infinite sequence of integers,
        // starting with n.
        let v = n;

        while (true) {
            yield v;
            v = 1 + v;
        }
    };


    // pred :: Int -> Int
    const pred = x =>
        x - 1;


    // scanlGen :: (b -> a -> b) -> b -> Gen [a] -> [b]
    const scanlGen = f =>
        // The series of interim values arising
        // from a catamorphism over an infinite list.
        startValue => function* (gen) {
            let
                a = startValue,
                x = gen.next();

            yield a;
            while (!x.done) {
                a = f(a)(x.value);
                yield a;
                x = gen.next();
            }
        };


    // succ :: Int -> Int
    const succ = x =>
        1 + x;


    // take :: Int -> [a] -> [a]
    // take :: Int -> String -> String
    const take = n =>
        // The first n elements of a list,
        // string of characters, or stream.
        xs => Array.from({
            length: n
        }, () => {
            const x = xs.next();

            return x.done ? [] : [x.value];
        }).flat();


    // MAIN ---
    return JSON.stringify(main(), null, 2);
})();

You may also check:How to resolve the algorithm Generate Chess960 starting position step by step in the Go programming language
You may also check:How to resolve the algorithm Call a function in a shared library step by step in the PowerBASIC programming language
You may also check:How to resolve the algorithm Ray-casting algorithm step by step in the R programming language
You may also check:How to resolve the algorithm Fractal tree step by step in the POV-Ray programming language
You may also check:How to resolve the algorithm Conditional structures step by step in the Amazing Hopper programming language