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