April 8, 2011
Note that there is no need of two dimensional array to memoization of partial results. This fact is evident from Pascal's triangle with an extra variable to store nCk.
We know that C (n, r) = C (n – 1, r – 1) + C (n – 1, r)
It is quite easy to prove it mathematically. But what is its significance in real life examples?
C (n, r) is selecting r elements from n elements. Pick a special element k from these n elements, we left with (n – 1) elements.
Now this r elements selection C (n, r) can be grouped into two categories,
A) r elements that contain the element k.
B) r elements that do not contain the element k.
From A) the special element k is in all r selections. Since k is part of r elements, we need to choose remaining (r – 1) elements from remaining (n – 1) elements, this can be done in C (n – 1, r – 1) ways.
From B) the special element k is not there in all r selections. It means, we will have to select all the r elements from available (n – 1) elements (we must exclude element k from n). This can be done in C (n – 1, r) ways.
Now it is evident that, the first term of RHS is combination containing special element k, and the second term is combination without the special element k. Sum of these two is selecting r elements from n elements.
Interesting proof, little confusing to understand, but useful in practice.
Pascal's Identity and Dynamic Programming:
If we note the identity, it is the base for recursive calculation of binomial coefficients. However, when plain recursion is used, it will lead to an exponential algorithm.
Recursion with memoization can result in an efficient algorithm. The idea behind this dynamic programming (programming we mean a method of tabulation) is to tabulate the first occurrence of binomial co-efficients.
Pascal's triangle can serve as the tabulation in the dynamic method. Each co-efficient is sum of coefficients in the previous row. The table can grow till min(k, i) where 0 <= i <= n.
Try the dynamic algorithm.
No comments:
Post a Comment