The Kitchen Sink and Other Oddities

Atabey Kaygun

Catalan's Triangle

Description of the Problem:

Today, I am going to write a common lisp function that returns the entries in Catalan’s Triangle. The description is an easy recursive function: \(C(n,k) = 0\) when \(n<1\), or \(k<1\), or \(n<k\). And we have \[ C(n,k) = C(n-1,k) + C(n,k-1) \] otherwise. The base case is \(C(1,1)=1\).

Implementation

If we were to implement this without memoization it would be very expansive to calculate the values of this function.

(defun dumb (n k)
  (cond ((or (< n 1) (< k 1) (< n k)) 0)
        ((= k 1) 1)
        (t (+ (dumb (1- n) k)
              (dumb n (1- k))))))
DUMB

Let me test:

(time (loop for i from 1 to 12 collect (dumb 12 i)))
Evaluation took:
  0.008 seconds of real time
  0.008000 seconds of total run time (0.008000 user, 0.000000 system)
  100.00% CPU
  20,438,732 processor cycles
  0 bytes consed

(1 11 65 273 910 2548 6188 13260 25194 41990 58786 58786)

So, I am going to re-implement it using a simple memoization trick:

(let ((table (make-hash-table :test #'equal)))
  (defun catalan (n k)
    (cond ((or (< n 1) (< k 1) (< n k)) 0)
          ((= k 1) 1)
          (t (or (gethash (list n k) table)
                 (setf (gethash (list n k) table)
                       (+ (catalan (1- n) k)
                          (catalan n (1- k)))))))))
CATALAN

Let us test:

(time (loop for i from 1 to 12 collect (catalan 12 i)))
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  47,122 processor cycles
  0 bytes consed

(1 11 65 273 910 2548 6188 13260 25194 41990 58786 58786)