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…
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 […]