Skip to content

Instantly share code, notes, and snippets.

@isomorphisms
Last active August 29, 2015 14:08
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save isomorphisms/cb65fec24ee4b13becca to your computer and use it in GitHub Desktop.
the Catalan numbers: recursive formula for # binary trees, # triangulations of a polygon, and more
catalan :: (Integral n) => n -> n -- not memoised
catalan 0 = 1
catalan n = sum [ catalan i * catalan(n-1-i) | i <- [0..n-1] ] --N:=n+1
catalan <- function(N) {
if (N==0) 1
else
n=N-1 #power of notation
#not memoised
lapply(0:n, FUN=function(i) catalan(i) * catalan(n-i) ) %>% unlist %>% sum
}
catalan <- function(n) {
#make a memo
if (!exists('cat.save') || length(cat.save) < n) { cat.save <<- integer(n) }
#actual catalan function
#base layer
if (n==0) 1
#recursive part
else {
#reuse
if (cat.save[n] !=0) { cat.save[n] }
else
#Catalan formula
(cat.save[n] <<- lapply(0:n, FUN=function(i) catalan(i-1) * catalan(n-i) ) %>% unlist %>% sum)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment