Catalan Numbers
September 12, 2017
Today’s exercise is an Amazon interview question for software engineers and developers:
How many unique binary search trees can be made from a series of numbers 1, 2, 3, 4, …, n, for any given n?
Your task is to compute the number of unique binary search trees. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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…
my $N = shift; my @T = (1,1); foreach my $t (2..$N) { my $x = 0; $x += $T[$_] * $T[$t-$_-1] foreach 0 .. $t-1; push @T, $x; } shift @T; print join "\n", q(), @T, q(),q();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.
def ntrees(): table = [1] yield from table for k in count(1): table.append(sum(table[split] * table[k-1-split] for split in range(k))) yield table[-1]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.
(import (scheme base) (scheme write)) (define (n-choose-k/cps n k return) (if (zero? k) (return 1) (n-choose-k/cps (- n 1) (- k 1) (lambda (result) (return (* n (/ result k))))))) (define (n-choose-k n k) (call-with-current-continuation (lambda (cont) (n-choose-k/cps n k cont)))) (define (cat-num n) (- (n-choose-k (* 2 n) n) (n-choose-k (* 2 n) (+ n 1)))) (display (cat-num 10000)) (newline)A very fast way to calcuate Catalan numbers and a more elegant version of my earlier solution.
def dotproduct(vec1, vec2): return sum(map(mul, vec1, vec2)) def ntrees(): table = [1] yield 1 # for n=0 while True: table.append(dotproduct(table, reversed(table))) yield table[-1] def catalan_g(): 'very fast way to calculate Catalan numbers' yield from (0, 1) c = 1 for n in count(1): c = c * 2 * (2*n + 1) // (n + 2) yield c[…] our exercise a week ago, I’ve been reading about Catalan numbers, primarily based on the references at […]