#-------------------------------------------------------------------------------
#  BinomialCoefficients.py
#-------------------------------------------------------------------------------


def BinCoeff(n, k):
   """
   Returns (n choose k), the number of k element subsets of an n-element set.
   """

   if k==0 or k==n: # what if caller has k<0 or k>n?
      return 1
   else:
      return BinCoeff(n-1, k-1) + BinCoeff(n-1, k)
   # end
# end

def BinCoeffMemo(n, k, Table):
   """
   Returns (n choose k), the number of k element subsets of an n-element set.
   Uses memoization, i.e. maintains a dictionary of previously computed results.
   """

   if k<=0 or k>=n:  
      return 1
   elif (n, k) in Table:
      return Table[(n, k)]
   else:
      val = BinCoeffMemo(n-1, k-1, Table) + BinCoeffMemo(n-1, k, Table)
      Table[(n,k)]= val
      return val
   # end
# end


#------------------------------------------------------------------------------
if __name__=='__main__':

   #"""
   # with no memoization
   print("(10 choose 5) =",  BinCoeff(10,5))
   print("(20 choose 10) =", BinCoeff(20, 10))
   print("(24 choose 12) =", BinCoeff(24, 12))
   print("(26 choose 13) =", BinCoeff(26, 13)) # takes about 3 seconds
   #print("(28 choose 14) =", BinCoeff(30, 15)) # takes about 34 seconds 
   #"""

   """
   # with memoization
   C = {} 

   # print(BinCoeffMemo(1000,500, C)) # exceeds recursion depth
   print()
   print("(400 choose 200) =\n", BinCoeffMemo(400,200, C), sep='', end='\n\n')

   # re-use that dictionary for subsequent calls
   print("(800 choose 400) =\n", BinCoeffMemo(800,400, C), sep='', end='\n\n')

   # does not exceed recursion depth
   print("(1000 choose 500) =\n", BinCoeffMemo(1000,500, C), sep='', end='\n\n') 
   print("(1400 choose 700) =\n", BinCoeffMemo(1400,700, C), sep='', end='\n\n') 

   print()
   # print(C)
   """

# end