binomial coefficients with dynamic programming

binomial.py

# binomial coefficients

"""
Recurrence relation:
	C(n,k) is the count of all k-subsets in a set of n items.
	C(n,k) = C(n-1,k-1) + C(n-1,k)
	
Intuition underlying the relation:
		1. pick any item from the n-set, call it the special item.
		2. Every k-subset either includes the special item or does not.
		3. How many k-subsets INCLUDE the item? The number of k-subsets which include it is the same as the number of (k-1)-subsets in the set of (n-1) items, since you are just adding the special item to every one of those.
		4. How many k-subsets do NOT include the item? The number of k-subsets which do not include it is the number of k-subsets you can make from the set of n-1 items, since you effectively have a set of (n-1) items once you do not include it when buiding sets.
		5. So, C(n,k) = C(n-1,k-1) + C(n-1,k)

base cases:
	1. C(n,1) == n, since there are n ways to pick a single item from a set of n items.
	2. C(n,n) == 1, since there is 1 way to pick all the items of a set
"""

# simple recursive implementation
#
# we call our function with the intended arguments, and the implementation recurses
# to compute earlier required values
#
# worst-case complexity: 
# - 2 branches under each node
# - every node is a function call. 
#  - every call allocates local storage.
#  - every call is one computation 
# - count(nodes) ~= 2^n
# - worst case depth: n
# - worst case
#
# TC: a^n ( 1 < a <= 2)
# SC: same, due to stack frame storage
def binom(n,k):
	if k == 1: return n
	if n == k: return 1
	if k == 0: return 1
	return binom(n-1,k-1) + binom(n-1,k)

# simple recursive implementation, with memoization to remove redundant computation
# (But this costs storage)
#
# we call the recursive function with the arguments, and the implementation
# recurses back to compute earlier required values only as needed
#
# TC: 
# SC:
def memo_binom(n,k):
	cache = {}
	def binom_in(n,k):
		if (n,k) in cache: return cache[(n,k)]
		retval = None
		if n == k: retval = 1
		elif k == 0: retval = 1
		else:
			retval = binom_in(n-1,k-1) + binom_in(n-1,k)
		cache[(n,k)] = retval
		return retval
	return binom_in(n,k)

# tabular implementation
#
# having studied the recursion tree from the earlier implementations, we can
# forsee which values need to be computed in order to get to our final desired
# value
#
# So now we iterate forward up to that value saving results as we go.
#
# (the fiddly part is working out the bounds for what k values to compute.)
#
# It seems to me this uses the same storage as the memoized recursive implementation
# except for some savings in not building a call stack, but then some additional
# storage for computing unnecessary parts of the table

# SC: O(nk)
# TC: O(nk)
def tabular_binom(n,k,verbose = False):
	dp=dict()
	for nn in range(n+1):
		dp[(nn,0)] = 1
	for kk in range(k+1):
		dp[(kk,kk)] = 1
	for nn in range(2,n+1):
		for kk in range(max(1,k-(n-nn)),min(nn,k+1)):
			dp[(nn,kk)] = dp[(nn-1,kk-1)] + dp[(nn-1,kk)]
	if verbose: print(f"storage used: {n}*{k}={n*k}")
	return dp[(n,k)]

# linear-space pseudo-tabular implementation
#
# Having studied our preceding tabular implementation, we can see that we don't
# need to remember all preceding values, only 2 rows of values.
#
# So we build a custom dictionary data structure, which computes boundary
# values, and otherwise is a cache to store only the last 2 rows of non-boundary 
# values that were set. Setting a value with a higher-than-prefiously-seen n
# dumps the older row and creates storage for a new one. This structure gives
# constant time access, but requires the predictable row at a time write then
# read access pattern which we use.

# SC: O(k)
# TC: O(nk)

class DPC:
	def __init__(self,k):
		self.hink = [None] * (k+1)
		self.lonk = [None] * (k+1)
		self.hin = 2
		self.lown = 1
	def get(self,nk):
		(n,k)=nk
		if k==0 or n==k: return 1
		else:
			if n != self.hin and n != self.lown:
				print("never set!")
				return None
			arr = self.hink if n == self.hin else self.lonk
			return arr[k]
	def set(self,nk,v):
		(n,k)=nk
		if k==0 or n==k: return
		else:
			if n > self.hin:
				(self.lown, self.hin) = (self.hin,n)
				(self.lonk, self.hink) = (self.hink,self.lonk)
				for i in range(len(self.hink)): self.hink[i] = None
			arr = self.hink if n == self.hin else self.lonk
			arr[k] = v
		
def const_binom(n,k,verbose=False):
	dpc = DPC(k)
	for nn in range(2,n+1):
		for kk in range(max(1,k-(n-nn)),min(nn,k+1)):
			a = dpc.get((nn-1,kk-1))
			b = dpc.get((nn-1,kk))
			dpc.set((nn,kk), a + b)
	if verbose: print(f"storage used: 2*{k}={2*k}")
	return dpc.get((n,k))

def printBinoms(n):
	for nn in range(0,n+1):
		print(f"{nn}: ",end="")
		for kk in range(0,nn+1):
			v = tabular_binom(nn,kk)
			print(f"{v}\t\t",end="")
		print("")

#printBinoms(10)