More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don't these these algorithms are the most efficient algorithms

# # dynamic programming for binomial co-efficient # def dynamic_bc(n, k, indent=0): # # return (n k) using dynamic programming # tail cases are k == 0 or k == 1 # (n 0) = 1 and (n 1) = n for i in range(0, indent): print " ", print "%d:%d" %(n, k) if (k == 0): arr[n][k] = 1 return 1 if (k == 1): arr[n][k] = n return n if (n == k): arr[n][k] = 1 return 1 # (n k) = (n!)/(n-k)!k!, lets split it further # n!/(n-k)!k! = n(n-1)!/(n-k)!k(k-1)! # or (n k) = (n-1 k) + (n -1 k-1) if (arr[n-1][k-1] == 0): arr[n-1][k-1] = dynamic_bc(n-1,k-1,indent+1) if (arr[n-1][k] == 0): arr[n-1][k] = dynamic_bc(n-1, k,indent+1) return arr[n-1][k] + arr[n-1][k-1] def bc(n, k, indent=0): # # tail cases are k == 0 or k == 1 # (n 0) = 1 and (n 1) = n for i in range(0, indent): print " ", print "%d:%d" %(n, k) if (k == 0): return 1 if (k == 1): return n if (n == k): return 1 # (n k) = (n!)/(n-k)!k!, lets split it further # n!/(n-k)!k! = n(n-1)!/(n-k)!k(k-1)! # or (n k) = (n-1 k) + (n -1 k-1) return bc(n-1,k,indent+1) + bc(n-1,k-1,indent+1) number = 6 select = 3 arr = [[0 for x in range(0, number)] for x in range(0, number)] print bc(number, select) print dynamic_bc(number, select)The output for the first call with full recursion

6:3 5:3 4:3 3:3 3:2 2:2 2:1 4:2 3:2 2:2 2:1 3:1 5:2 4:2 3:2 2:2 2:1 3:1 4:1 20The output for For the first call with full recursion

6:3 5:2 4:1 4:2 3:1 3:2 2:1 2:2 5:3 4:3 3:3 20Python supports memoization via functools (wraps, lru_cache, etc). I am using the wrapper (decorator pattern). Using the following pattern makes the programming so transparent

# # dynamic programming for binomial co-efficient # from functools import wraps def dynamic_bc2(func): cache = {} def wrap(*args): if args not in cache: cache[args] = func(*args) return cache[args] return wrap @dynamic_bc2 def bc2(n, k, indent=0): # # return (n k) using dynamic programming # tail cases are k == 0 or k == 1 # (n 0) = 1 and (n 1) = n for i in range(0, indent): print " ", print "%d:%d" %(n, k) if (k == 0): return 1 if (k == 1): return n if (n == k): return 1 # (n k) = (n!)/(n-k)!k!, lets split it further # n!/(n-k)!k! = n(n-1)!/(n-k)!k(k-1)! # or (n k) = (n-1 k) + (n -1 k-1) return bc2(n-1,k-1,indent+1) + bc2(n-1,k,indent+1) number = 6 select = 3 print bc2(number, select)Comparing the output will show the affect of functools. The output with functools is:

6:3 5:2 4:1 4:2 3:1 3:2 2:1 2:2 5:3 4:3 3:3 20