{"id":26046,"date":"2017-10-26T19:39:45","date_gmt":"2017-10-26T14:09:45","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26046"},"modified":"2017-10-26T19:39:45","modified_gmt":"2017-10-26T14:09:45","slug":"c-programming-binomial-coefficient","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-binomial-coefficient\/","title":{"rendered":"C Programming &#8211; Binomial Coefficient"},"content":{"rendered":"<p>Following are common definition of Binomial Coefficients.<br \/>\n1) A binomial coefficient C(n, k) can be defined as the coefficient of X^k in the expansion of (1 + X)^n.<span id=\"more-17806\"><\/span><\/p>\n<p>2) A binomial coefficient C(n, k) 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<p><strong>The Problem<\/strong><br \/>\n<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><strong>Optimal Substructure<\/strong><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[ad type=\u201dbanner\u201d]\n<p>Following is a simple recursive implementation that simply follows the recursive structure mentioned above.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20Naive%20Recursive%20Implementation%0A%23include%3Cstdio.h%3E%0A%20%0A%2F%2F%20Returns%20value%20of%20Binomial%20Coefficient%20C(n%2C%20k)%0Aint%20binomialCoeff(int%20n%2C%20int%20k)%0A%7B%0A%20%20%2F%2F%20Base%20Cases%0A%20%20if%20(k%3D%3D0%20%7C%7C%20k%3D%3Dn)%0A%20%20%20%20return%201%3B%0A%20%0A%20%20%2F%2F%20Recur%0A%20%20return%20%20binomialCoeff(n-1%2C%20k-1)%20%2B%20binomialCoeff(n-1%2C%20k)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20int%20n%20%3D%205%2C%20k%20%3D%202%3B%0A%20%20%20%20printf(%22Value%20of%20C(%25d%2C%20%25d)%20is%20%25d%20%22%2C%20n%2C%20k%2C%20binomialCoeff(n%2C%20k))%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<ul>\n<li><strong>Overlapping Subproblems<\/strong><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 Overlapping Subproblems property. 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 Dynamic Programming based implementation.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20Dynamic%20Programming%20based%20solution%20that%20uses%20table%20C%5B%5D%5B%5D%20to%0A%2F%2F%20calculate%20the%20Binomial%20Coefficient%0A%23include%3Cstdio.h%3E%0A%20%0A%2F%2F%20Prototype%20of%20a%20utility%20function%20that%20returns%20minimum%20of%20two%20integers%0Aint%20min(int%20a%2C%20int%20b)%3B%0A%20%0A%2F%2F%20Returns%20value%20of%20Binomial%20Coefficient%20C(n%2C%20k)%0Aint%20binomialCoeff(int%20n%2C%20int%20k)%0A%7B%0A%20%20%20%20int%20C%5Bn%2B1%5D%5Bk%2B1%5D%3B%0A%20%20%20%20int%20i%2C%20j%3B%0A%20%0A%20%20%20%20%2F%2F%20Caculate%20value%20of%20Binomial%20Coefficient%20in%20bottom%20up%20manner%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(j%20%3D%200%3B%20j%20%3C%3D%20min(i%2C%20k)%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Base%20Cases%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(j%20%3D%3D%200%20%7C%7C%20j%20%3D%3D%20i)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20C%5Bi%5D%5Bj%5D%20%3D%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Calculate%20value%20using%20previosly%20stored%20values%0A%20%20%20%20%20%20%20%20%20%20%20%20else%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%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20C%5Bn%5D%5Bk%5D%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20return%20minimum%20of%20two%20integers%0Aint%20min(int%20a%2C%20int%20b)%0A%7B%0A%20%20%20%20return%20(a%3Cb)%3F%20a%3A%20b%3B%0A%7D%0A%20%0A%2F*%20Drier%20program%20to%20test%20above%20function*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20int%20n%20%3D%205%2C%20k%20%3D%202%3B%0A%20%20%20%20printf%20(%22Value%20of%20C(%25d%2C%20%25d)%20is%20%25d%20%22%2C%20n%2C%20k%2C%20binomialCoeff(n%2C%20k)%20)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>Value of C[5][2] is 10<\/pre>\n<p>Time Complexity: O(n*k)<br \/>\nAuxiliary Space: O(n*k)<\/p>\n[ad type=\u201dbanner\u201d]\n<p>Following is a space optimized version of the above code. The following code only uses O(k).<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20for%20space%20optimized%20Dynamic%20Programming%0A%2F%2F%20Solution%20of%20Binomial%20Coefficient%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0Aint%20binomialCoeff(int%20n%2C%20int%20k)%0A%7B%0A%20%20%20%20int%20C%5Bk%2B1%5D%3B%0A%20%20%20%20memset(C%2C%200%2C%20sizeof(C))%3B%0A%20%0A%20%20%20%20C%5B0%5D%20%3D%201%3B%20%20%2F%2F%20nC0%20is%201%0A%20%0A%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Compute%20next%20row%20of%20pascal%20triangle%20using%0A%20%20%20%20%20%20%20%20%2F%2F%20the%20previous%20row%0A%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%20min(i%2C%20k)%3B%20j%20%3E%200%3B%20j\u2013)%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%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20C%5Bk%5D%3B%0A%7D%0A%20%0A%2F*%20Drier%20program%20to%20test%20above%20function*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20int%20n%20%3D%205%2C%20k%20%3D%202%3B%0A%20%20%20%20printf%20(%22Value%20of%20C(%25d%2C%20%25d)%20is%20%25d%20%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20n%2C%20k%2C%20binomialCoeff(n%2C%20k)%20)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>Value of C[5][2] is 10<\/pre>\n<p>Time Complexity: O(n*k)<br \/>\nAuxiliary Space: O(k)<\/p>\n<p>Explanation:<br \/>\n1==========>> n = 0, C(0,0) = 1<br \/>\n1\u20131========>> n = 1, C(1,0) = 1, C(1,1) = 1<br \/>\n1\u20132\u20131======>> n = 2, C(2,0) = 1, C(2,1) = 2, C(2,2) = 1<br \/>\n1\u20133\u20133\u20131====>> n = 3, C(3,0) = 1, C(3,1) = 3, C(3,2) = 3, C(3,3)=1<br \/>\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<br \/>\nSo here every loop on i, builds i\u2019th row of pascal triangle, using (i-1)th row<\/p>\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 Pascal\u2019s triangle 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>C 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":[83612,69866,1,70145],"tags":[76723,76721,76727,76728,75842,76725,76726,76719,76718,76722,76724,76720,72847,72842,72845,70483,72848,72840,72846,72987,72843,72992,72844,72850,72839,72852,72853,72851],"class_list":["post-26046","post","type-post","status-publish","format-standard","hentry","category-binomial-coefficient","category-c-programming","category-coding","category-dynamic-programming","tag-algorithm-for-binomial-coefficient","tag-binomial-coefficient-dynamic-programming-java","tag-binomial-coefficient-examples","tag-binomial-coefficient-in-c","tag-binomial-coefficient-in-c-program","tag-binomial-coefficient-problems","tag-binomial-coefficient-properties","tag-binomial-coefficient-time-complexity","tag-binomial-coefficient-using-dynamic-programming-in-c","tag-c-program-for-binomial-coefficient-using-dynamic-programming","tag-c-program-for-binomial-coefficient-using-recursion","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-java","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-types-of-dynamic-programming","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26046","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=26046"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26046\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26046"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26046"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26046"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}