Dynamic programming of choose(n,k) in Python

by Forrest Sheng Bao http://fsbao.net

This code is licensed under GPL v3 or later. And you know what you cannot do and what you can do with it.
If you don't know what choose is and its relationship with dynamic programming, check this out http://en.wikipedia.org/wiki/Binomial_coefficient

from numpy import *

def choose(n,k):
   A = zeros((n+1,k+1))
   A[:,0] = 1
   A[1,1] = 1
   for j in xrange(1,k+1): # j = 2:k
      for i in xrange(j,n+1): # i = j:n
         A[i,j] = A[i-1,j-1] + A[i-1,j]
   print A
   return(A[n,k])
 
Example:
 
>>> choose(6,3)
[[  1.   0.   0.   0.]
 [  1.   1.   0.   0.]
 [  1.   2.   1.   0.]
 [  1.   3.   3.   1.]
 [  1.   4.   6.   4.]
 [  1.   5.  10.  10.]
 [  1.   6.  15.  20.]]

No comments: