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

Published on 12 May 2024 09:40 PM
#Python

How to resolve the algorithm Catalan numbers step by step in the Python 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 Python programming language

First Code

This code calculates the Catalan numbers, which are a sequence of natural numbers that appear in many combinatorial problems, like counting the number of ways to partition a polygon into triangles.

The code defines three functions that calculate the nth Catalan number using different methods:

  1. cat_direct uses the direct formula for the nth Catalan number: (C_n = \frac{1}{n+1}\binom{2n}{n}).

  2. catR1 uses a recursive formula with memoization: (C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}).

  3. catR2 also uses a recursive formula with memoization: (C_n = \frac{4n-2}{n+1} C_{n-1}).

The memoize decorator is used to ensure that the recursive functions only calculate each Catalan number once, improving performance.

Second Code

This code also calculates the Catalan numbers, but it uses a different approach:

  1. It defines a function catalans3 that generates an infinite sequence of Catalan numbers using a generator expression.
  2. The generator expression uses the function go to calculate the next Catalan number based on the previous ones.
  3. The accumulate function is used to accumulate the Catalan numbers into a list.

The main function prints the first 15 Catalan numbers using the catalans3 generator.

Overall

Both codes calculate the Catalan numbers, but they use different approaches and formulas. The second code is more efficient for generating a large number of Catalan numbers, while the first code is more straightforward and easier to understand.

Source code in the python programming language

from math import factorial
import functools


def memoize(func):
    cache = {}

    def memoized(key):
        # Returned, new, memoized version of decorated function
        if key not in cache:
            cache[key] = func(key)
        return cache[key]
    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 % (('=' * 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)


'''Catalan numbers'''

from itertools import accumulate, chain, count, islice


# catalans3 :: [Int]
def catalans3():
    '''Infinite sequence of Catalan numbers
    '''
    def go(c, n):
        return 2 * c * pred(2 * n) // succ(n)

    return accumulate(
        chain([1], count(1)), go
    )


# ------------------------- TEST -------------------------
# main :: IO ()
def main():
    '''Catalan numbers, definition 3'''
    print("Catalans 1-15:\n")
    print(
        '\n'.join([
            f'{n:>10}' for n
            in islice(catalans3(), 15)
        ])
    )


# ----------------------- GENERIC ------------------------

# pred :: Int -> Int
def pred(n):
    '''Predecessor function'''
    return n - 1


# succ :: Int -> Int
def succ(n):
    '''Successor function'''
    return 1 + n


# MAIN ---
if __name__ == '__main__':
    main()

You may also check:How to resolve the algorithm Probabilistic choice step by step in the Rust programming language
You may also check:How to resolve the algorithm Binary digits step by step in the Elixir programming language
You may also check:How to resolve the algorithm Partition an integer x into n primes step by step in the Sidef programming language
You may also check:How to resolve the algorithm Add a variable to a class instance at runtime step by step in the Swift programming language
You may also check:How to resolve the algorithm Four bit adder step by step in the AutoIt programming language