Introduction

The Catalan numbers are a sequence of natural numbers that have important applications in several fields such as combinatorics, algebra, geometry and several other branches of mathematics. This sequence is named after Eugène Charles Catalan, a Belgian mathematician. Catalan numbers describe the number of ways to perform several tasks such as arranging brackets in expressions, forming triangulations from non-convex polygons, arranging ball sequences, etc.

Implementation


(* Catalan numbers *)

let imp_catalan n =
  let return = ref 1 in
  for i = 1 to n do
    return := !return * 2 * (2 * i - 1) / (i + 1)
  done;
  !return

let rec catalan = function
  | 0 -> 1
  | n -> catalan (n - 1) * 2 * (2 * n - 1) / (n + 1)

let memoize f =
  let cache = Hashtbl.create 20 in
  fun n ->
    match Hashtbl.find_opt cache n with
    | None ->
      let x = f n in
      Hashtbl.replace cache n x;
      x
    | Some x -> x

let catalan_cache = Hashtbl.create 20

let rec memo_catalan n =
  if n = 0 then 1 else
    match Hashtbl.find_opt catalan_cache n with
    | None ->
      let x = memo_catalan (n - 1) * 2 * (2 * n - 1) / (n + 1) in
      Hashtbl.replace catalan_cache n x;
      x
    | Some x -> x

let () =
  if not !Sys.interactive then
    let bench label f n times =
      let start = Unix.gettimeofday () in
      begin
        for i = 1 to times do f n done;
        let stop = Unix.gettimeofday () in
        Printf.printf "%s (%d runs) : %.3f
"
          label times (stop -. start)
      end in
    let show f g h f' n =
      for i = 0 to n do
        Printf.printf "%2d %7d %7d %7d %7d
"
          i (f i) (g i) (h i) (f' i)
      done
    in
    List.iter (fun (l, f) -> bench l f 15 10_000_000)
      ["imperative", imp_catalan;
       "recursive", catalan;
       "hand-memoized", memo_catalan;
       "memoized", (memoize catalan)];
    show imp_catalan catalan memo_catalan (memoize catalan) 15

The algorithm calculates the Catalan number using four different implementation methods:

  • imp_catalan calculates Catalan numbers using imperative programming
  • catalan calculates Catalan numbers using a recursive algorithm
  • memoize constructs a memoized function
  • memo_catalan calculates Catalan numbers by memoization using the memoize function constructed above

Step-by-Step Explanation

  1. In imp_catalan, a reference value return is initialized to 1.
  2. A for-loop runs from 1 to n.
  3. For each iteration, return is updated as follows:
    • multiplied by 2
    • multiplied by 2i-1 (where i is the current iteration number)
    • divided by i+2

  4. Finally, !return (i.e., the value in the reference return) is returned.

  5. In catalan, the function takes an integer argument n.
  6. If n is zero, the function returns one, else it calculates and returns the Catalan number recursively as follows:
    • call catalan with (n-1) as argument
    • multiply the result of the recursive call by 2
    • multiply it by 2n-1
    • divide it by n+1
  7. In memoize, the function takes as input another function f.
  8. The result is a new function that caches the output of f for a given input n.
  9. First, a cache hash table is created to hold the function values.
  10. The new function takes as input an argument n, and first checks if the value for this input is already in the cache.
  11. If it is not in the cache, the original function f is applied to n, and the result is stored in the cache.

  12. Finally, the function returns the value either found in the cache or computed by f.

  13. In memo_catalan, the function takes the argument n.
  14. If the input is 0, the function returns 1.
  15. Otherwise, it checks if the value is already in the cache.
  16. If the value is not in the cache, calculate the Catalan number recursively using (n-1), multiplied by 2, multiplied by 2n-1, and divided by n+1.

  17. The calculated value is then stored in the cache and returned.

  18. show function prints out a table of Catalan numbers for the first n integers, computing the results using various methods.

Complexity Analysis

  • The time complexity of imp_catalan is O(n) since the for-loop runs for n iterations.
  • The time complexity of catalan is O(2^n) since it solves the problem recursively.
  • The time complexity of memo_catalan is O(n) since it computes n values recursively before reusing previously memoized solutions.
  • The time complexity of memoize is O(n) since the memoization table holds a maximum of n values.
  • The space complexity of imp_catalan, catalan, memoize, and memo_catalan is O(1) as they require a constant amount of memory to compute each Catalan number.