## Sunday, July 09, 2017

### Dynamic programming for the binomial coefficient

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
20


The 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
20

Python 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