Catalan Numbers
September 12, 2017
I wouldn’t get the job. The first thing I thought of was 2n − 1, but I quickly realized that was wrong. Then I set about drawing the first few sets of search trees, and realized I wasn’t getting anywhere. Then I looked at the answer:
(define (choose n k) ; binomial theorem (if (zero? k) 1 (* n (/ k) (choose (- n 1) (- k 1)))))
(define (catalan n) (if (zero? n) 1 (- (choose (+ n n) n) (choose (+ n n) (- n 1)))))
If you don’t like to compute those huge factorials, you can instead perform a dynamic programming calculation, using define-memoized
from a previous exercise:
(define-memoized (catalan n) (if (zero? n) 1 (let loop ((i 1) (count 0)) (if (< n i) count (loop (+ i 1) (+ count (* (catalan (- i 1)) (catalan (- n i)))))))))
The number of unique binary search trees that can be made from the integers from 1 to n is (catalan n)
, and it grows at a phenomally high rate:
> (do ((i 0 (+ i 1))) ((< 30 i)) (display i) (display #\tab) (display (catalan i)) (newline)) 0 1 1 1 2 2 3 5 4 14 5 42 6 132 7 429 8 1430 9 4862 10 16796 11 58786 12 208012 13 742900 14 2674440 15 9694845 16 35357670 17 129644790 18 477638700 19 1767263190 20 6564120420 21 24466267020 22 91482563640 23 343059613650 24 1289904147324 25 4861946401452 26 18367353072152 27 69533550916004 28 263747951750360 29 1002242216651368 30 3814986502092304
You can run the program at https://ideone.com/KM5smO.
Although I didn’t know it, Catalan numbers are ubiquitous in combinatorics; Sloane says “This is probably the longest entry in the OEIS, and rightly so.” Go to A000108 to look at it yourself.
I would be astonished at the candidate who answered that correctly.
Came up with the solution below… after looking at the graphs realised that
Tn = Sum (0..n-1) T[i] T[n-i-1]
{where T[0] = 1, T[1] = 1}
e,g,
T2 = T0T1 + T1T0
T3 = T1T2 + T1T1 + T2T0
…
Then came up with the following solution…
A dynamic solution in Python (same method as @James Curtis-Smith). For n elements, you can split the range by taking out 1 element (the split). Then you have a number of elements at the left and a number on the right, so you can reduce the problem if you have calculated all case smaller than n already.
Forgot to say – the logic to the calculation is that you chose each element in turn for the fist element – other elements are either smaller larger than the current element {assuming no dupes}. We set the node as root and work out what trees are to the left or right…
Smallest element:0 element tree to left : (n-1)-element tree to right – count is therefore T0 * T(n-1)
Next element:1 element tree to left : (n-2)-element tree to right
…
Next element:(n-1) element tree to left : 0 element tree to right- count is therefore T(n-1) * T0
Blog post from a while back: http://grahamenos.com/stanley-catalan.html
Once we map the problem to Catalan numbers (the title gives it away!)
the main challenge may be calculating those numbers. The sample
solution by @programmingpraxis works for modest values of n but for
much larger values we can use the following, in standard (R7RS)
Scheme. It runs in a few seconds with Larceny Scheme on my very modest
computer.
A very fast way to calcuate Catalan numbers and a more elegant version of my earlier solution.
[…] our exercise a week ago, I’ve been reading about Catalan numbers, primarily based on the references at […]