What you want to do is automate the process of cancelling common factors that you would do if you were calculating nCr by hand. Fill an array a[] with the numerator terms, n, n-1, n-2, ..., n-r+1, and a second array b[] with the denominator terms, 1, 2, 3, ..., r. Inside a double loop with j and i going from 0 to r-1, compute the gcd of a[i] and b[j]. Divide both a[i] and b[j] by the gcd. When the loops finish, you will have cancelled the common factors from all of the terms, and in fact, all of the denominator terms will be 1. In a final loop, compute the product of the numerator terms. There are some obvious optimizations.
Dave On Tuesday, April 8, 2014 1:06:47 PM UTC-5, kumar raja wrote: > Hi all, > > I know the way to calculate value of C(n,r) using pascals identity. But i > have a different requirement. > > C(n,r) = n (n-1) (n-2) ... (n-r+1) / r! > > Suppose the numerator is such that it cant fit into existing data type. > > So i remember there is a way to strike off the common factors in numerator > and denominator then calculate the result of it. But the logic is not > striking to me. Googled but could not find much. So please share the clever > way to calculate the above value w/o actually computing the factorials and > then making division. > > My actual requirement is to calculate the value of > > (n1+n2+....+nk)! / (n1!.n2!.n3!.....nk!) . > > > Regards, > Kumar Raja. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
