{"id":26053,"date":"2017-10-26T19:40:22","date_gmt":"2017-10-26T14:10:22","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26053"},"modified":"2018-10-31T13:18:18","modified_gmt":"2018-10-31T07:48:18","slug":"python-programming-binomial-coefficient","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-binomial-coefficient\/","title":{"rendered":"Python Programming &#8211; Binomial Coefficient"},"content":{"rendered":"<h3 id=\"following-are-common-definition-of-binomial-coefficients\"><span style=\"color: #003300;\">Following are common definition of Binomial Coefficients:<\/span><\/h3>\n<p>1) A binomial coefficient <strong>C(n, k)<\/strong> can be defined as the coefficient of <strong>X^k<\/strong> in the expansion of <strong>(1 + X)^n.<\/strong><span id=\"more-17806\"><\/span><\/p>\n<p>2) A <a href=\"https:\/\/www.wikitechy.com\/technology\/java-programming-space-time-efficient-binomial-coefficient\/\" target=\"_blank\" rel=\"noopener\">binomial coefficient<\/a> <strong>C(n, k)<\/strong> also gives the number of ways, disregarding order, that k objects can be chosen from among n objects; more formally, the number of k-element subsets (or k-combinations) of an n-element set.<\/p>\n<h2 id=\"the-problem\"><span style=\"color: #ff0000;\"><strong>The Problem<\/strong><\/span><\/h2>\n<p><em>Write a function that takes two parameters n and k and returns the value of Binomial Coefficient C(n, k).<\/em> For example, your function should return 6 for n = 4 and k = 2, and it should return 10 for n = 5 and k = 2.<\/p>\n<ul>\n<li><span style=\"color: #003366;\"><strong>Optimal Substructure<\/strong><\/span><br \/>\nThe value of C(n, k) can be recursively calculated using following standard formula for Binomial Coefficients.<\/li>\n<\/ul>\n<pre>   C(n, k) = C(n-1, k-1) + C(n-1, k)\r\n   C(n, 0) = C(n, n) = 1\r\n<\/pre>\n<p>Following is a simple recursive implementation that simply follows the recursive structure mentioned above.<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20A%20naive%20recursive%20Python%20implementation%0A%20%0Adef%20binomialCoeff(n%20%2C%20k)%3A%0A%20%0A%20%20%20%20if%20k%3D%3D0%20or%20k%20%3D%3Dn%20%3A%0A%20%20%20%20%20%20%20%20return%201%0A%20%0A%20%20%20%20%23%20Recursive%20Call%0A%20%20%20%20return%20binomialCoeff(n-1%20%2C%20k-1)%20%2B%20binomialCoeff(n-1%20%2C%20k)%0A%20%0A%23%20Driver%20Program%20to%20test%20ht%20above%20function%0An%20%3D%205%0Ak%20%3D%202%0Aprint%20%22Value%20of%20C(%25d%2C%25d)%20is%20(%25d)%22%20%25(n%20%2C%20k%20%2C%20binomialCoeff(n%20%2C%20k))\u201d message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output\"><span style=\"color: #008000;\">Output:<\/span><\/h3>\n<pre>Value of C(5,2) is 10<\/pre>\n<ul>\n<li><span style=\"color: #003366;\"><strong>Overlapping Subproblems<\/strong><\/span><br \/>\nIt should be noted that the above function computes the same subproblems again and again. See the following recursion tree for n = 5 an k = 2. The function C(3, 1) is called two times. For large values of n, there will be many common subproblems.<\/li>\n<\/ul>\n<pre>                             C(5, 2)\r\n                    \/                      \\\r\n           C(4, 1)                           C(4, 2)\r\n            \/   \\                          \/           \\\r\n       C(3, 0)   C(3, 1)             C(3, 1)               C(3, 2)\r\n                \/    \\               \/     \\               \/     \\\r\n         C(2, 0)    C(2, 1)      C(2, 0) C(2, 1)          C(2, 1)  C(2, 2)\r\n                   \/        \\              \/   \\            \/    \\\r\n               C(1, 0)  C(1, 1)      C(1, 0)  C(1, 1)   C(1, 0)  C(1, 1)\r\n<\/pre>\n<p>Since same suproblems are called again, this problem has<a href=\"https:\/\/www.wikitechy.com\/technology\/python-programming-overlapping-subproblems-property\/\" target=\"_blank\" rel=\"noopener\"> Overlapping Subproblems property<\/a>. So the Binomial Coefficient problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, re-computations of same subproblems can be avoided by constructing a temporary array C[][] in bottom up manner. Following is <a href=\"https:\/\/www.wikitechy.com\/technology\/python-programming-program-fibonacci-numbers\/\" target=\"_blank\" rel=\"noopener\">Dynamic Programming<\/a> based implementation.<\/p>\n[ad type=\u201dbanner\u201d]\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20A%20Dynamic%20Programming%20based%20Python%20Program%20that%20uses%20table%20C%5B%5D%5B%5D%0A%23%20to%20calculate%20the%20Binomial%20Coefficient%0A%20%0A%23%20Returns%20value%20of%20Binomial%20Coefficient%20C(n%2C%20k)%0Adef%20binomialCoef(n%2C%20k)%3A%0A%20%20%20%20C%20%3D%20%5B%5B0%20for%20x%20in%20range(k%2B1)%5D%20for%20x%20in%20range(n%2B1)%5D%0A%20%0A%20%20%20%20%23%20Calculate%20value%20of%20Binomial%20Coefficient%20in%20bottom%20up%20manner%0A%20%20%20%20for%20i%20in%20range(n%2B1)%3A%0A%20%20%20%20%20%20%20%20for%20j%20in%20range(min(i%2C%20k)%2B1)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Base%20Cases%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20j%20%3D%3D%200%20or%20j%20%3D%3D%20i%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20C%5Bi%5D%5Bj%5D%20%3D%201%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Calculate%20value%20using%20previosly%20stored%20values%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20C%5Bi%5D%5Bj%5D%20%3D%20C%5Bi-1%5D%5Bj-1%5D%20%2B%20C%5Bi-1%5D%5Bj%5D%0A%20%0A%20%20%20%20return%20C%5Bn%5D%5Bk%5D%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0An%20%3D%205%0Ak%20%3D%202%0Aprint(%22Value%20of%20C%5B%22%20%2B%20str(n)%20%2B%20%22%5D%5B%22%20%2B%20str(k)%20%2B%20%22%5D%20is%20%22%0A%20%20%20%20%20%20%2B%20str(binomialCoef(n%2Ck)))%0A%20\u2033 message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output-2\"><span style=\"color: #008000;\">Output:<\/span><\/h3>\n<pre>Value of C[5][2] is 10<\/pre>\n<p><span style=\"color: #0000ff;\"><strong>Time Complexity:<\/strong><\/span> <strong>O(n*k)<\/strong><br \/>\n<span style=\"color: #0000ff;\"><strong>Auxiliary Space:<\/strong><\/span> <strong>O(n*k)<\/strong><\/p>\n<p>Following is a space optimized version of the above code. The following code only uses <strong>O(k).<\/strong><\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20for%20Optimized%20Dynamic%20Programming%20solution%20to%0A%23%20Binomail%20Coefficient.%20This%20one%20uses%20the%20concept%20of%20pascal%0A%23%20Triangle%20and%20less%20memory%0A%20%0Adef%20binomialCoeff(n%20%2C%20k)%3A%0A%20%0A%20%20%20%20%23%20Declaring%20an%20empty%20array%0A%20%20%20%20C%20%3D%20%5B0%20for%20i%20in%20xrange(k%2B1)%5D%0A%20%20%20%20C%5B0%5D%20%3D%201%20%23since%20nC0%20is%201%0A%20%0A%20%20%20%20for%20i%20in%20range(1%2Cn%2B1)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20Compute%20next%20row%20of%20pascal%20triangle%20using%0A%20%20%20%20%20%20%20%20%23%20the%20previous%20row%0A%20%20%20%20%20%20%20%20j%20%3D%20min(i%20%2Ck)%0A%20%20%20%20%20%20%20%20while%20(j%3E0)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20C%5Bj%5D%20%3D%20C%5Bj%5D%20%2B%20C%5Bj-1%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20j%20-%3D%201%0A%20%0A%20%20%20%20return%20C%5Bk%5D%0A%20%0A%23%20Driver%20Program%20to%20test%20the%20above%20function%0An%20%3D%205%0Ak%20%3D%202%0Aprint%20%22Value%20of%20C(%25d%2C%25d)%20is%20%25d%22%20%25(n%2Ck%2CbinomialCoeff(n%2Ck))\u201d message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output-3\"><span style=\"color: #008000;\">Output:<\/span><\/h3>\n<pre>Value of C(5)(2) is 10<\/pre>\n<p><span style=\"color: #3366ff;\"><strong>Time Complexity: <span style=\"color: #000000;\">O(n*k)<\/span><\/strong><\/span><br \/>\n<strong><span style=\"color: #3366ff;\">Auxiliary Space:<\/span> O(k)<\/strong><\/p>\n<h3 id=\"explanation\"><span style=\"color: #993366;\">Explanation:<\/span><\/h3>\n<pre>1==========>> n = 0, C(0,0) = 1\r\n1\u20131========>> n = 1, C(1,0) = 1, C(1,1) = 1\r\n1\u20132\u20131======>> n = 2, C(2,0) = 1, C(2,1) = 2, C(2,2) = 1\r\n1\u20133\u20133\u20131====>> n = 3, C(3,0) = 1, C(3,1) = 3, C(3,2) = 3, C(3,3)=1\r\n1\u20134\u20136\u20134\u20131==>> n = 4, C(4,0) = 1, C(4,1) = 4, C(4,2) = 6, C(4,3)=4, C(4,4)=1\r\nSo here every loop on i, builds i\u2019th row of pascal triangle, using (i-1)th row<\/pre>\n<p>At any time, every element of array C will have some value (ZERO or more) and in next iteration, value for those elements comes from previous iteration.<br \/>\nIn statement,<br \/>\nC[j] = C[j] + C[j-1]\nRight hand side represents the value coming from previous iteration (A row of <a href=\"https:\/\/www.wikitechy.com\/technology\/c-program-to-print-pascal-triangle\/\" target=\"_blank\" rel=\"noopener\">Pascal\u2019s triangle<\/a> depends on previous row). Left Hand side represents the value of current iteration which will be obtained by this statement.<\/p>\n[ad type=\u201dbanner\u201d]\n<pre>Let's say we want to calculate C(4, 3), \r\ni.e. n=4, k=3:\r\n\r\nAll elements of array C of size 4 (k+1) are\r\ninitialized to ZERO.\r\n\r\ni.e. C[0] = C[1] = C[2] = C[3] = C[4] = 0;\r\nThen C[0] is set to 1\r\n\r\nFor i = 1:\r\nC[1] = C[1] + C[0] = 0 + 1 = 1 ==>> C(1,1) = 1\r\n\r\nFor i = 2:\r\nC[2] = C[2] + C[1] = 0 + 1 = 1 ==>> C(2,2) = 1\r\nC[1] = C[1] + C[0] = 1 + 1 = 2 ==>> C(2,2) = 2\r\n\r\nFor i=3:\r\nC[3] = C[3] + C[2] = 0 + 1 = 1 ==>> C(3,3) = 1\r\nC[2] = C[2] + C[1] = 1 + 2 = 3 ==>> C(3,2) = 3\r\nC[1] = C[1] + C[0] = 2 + 1 = 3 ==>> C(3,1) = 3\r\n\r\nFor i=4:\r\nC[4] = C[4] + C[3] = 0 + 1 = 1 ==>> C(4,4) = 1\r\nC[3] = C[3] + C[2] = 1 + 3 = 4 ==>> C(4,3) = 4\r\nC[2] = C[2] + C[1] = 3 + 3 = 6 ==>> C(4,2) = 6\r\nC[1] = C[1] + C[0] = 3 + 1 = 4 ==>> C(4,1) = 4\r\n\r\nC(4,3) = 4 is would be the answer in our example.<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Python Programming &#8211; Binomial Coefficient &#8211; Dynamic Programming binomial coefficient can be defined as the coefficient of X^k in the expansion of (1 + X)^n<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,70145,4148],"tags":[76723,76735,76727,76739,76737,76725,76726,76719,76734,76720,72847,72842,72845,70483,72848,72840,72846,72994,72843,72992,72844,72850,72839,72852,76736,76738,72853,72851],"class_list":["post-26053","post","type-post","status-publish","format-standard","hentry","category-coding","category-dynamic-programming","category-python","tag-algorithm-for-binomial-coefficient","tag-binomial-coefficient-dynamic-programming-python","tag-binomial-coefficient-examples","tag-binomial-coefficient-in-python","tag-binomial-coefficient-in-python-program","tag-binomial-coefficient-problems","tag-binomial-coefficient-properties","tag-binomial-coefficient-time-complexity","tag-binomial-coefficient-using-dynamic-programming-in-python","tag-computing-binomial-coefficients-using-dynamic-programming","tag-concept-of-dynamic-programming","tag-define-dynamic-programming","tag-definition-of-dynamic-programming","tag-dynamic-programming","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-in-python","tag-dynamic-programming-problems","tag-dynamic-programming-python","tag-dynamic-programming-software","tag-explain-dynamic-programming","tag-how-to-solve-dynamic-programming-problems","tag-problems-on-dynamic-programming","tag-python-program-for-binomial-coefficient-using-dynamic-programming","tag-python-program-for-binomial-coefficient-using-recursion","tag-types-of-dynamic-programming","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26053","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26053"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26053\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26053"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26053"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26053"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}