The nice thing about combinations is that lots of stuff cancel out.
e.g.
10 C 6 = (10!) / (4! * 6!)
You can rewrite that as:
(10 * 9 * 8 * 7) / (4!)
I haven't really given it much thought, but off the top of my head I'd just resort to just canceling terms:
Java:
// Calculates n * (n - 1) * (n - 2) * ... k
private static long partialFactorial(int n, int k) {
long result = n;
for (int i = (n-1); i >= k; i--) {
result = result * i;
}
return result;
}
// Calculates the full factorial
// mine is a little different, calculates backward
private static long factorial(int n) {
long result = n;
for (int i = (n-1); i > 1; i--) {
result = result * i;
}
return result;
}
// n choose r
private static long nCr2(int n, int r) {
long numerator;
long denominator;
if ((n - r) > r) {
numerator = partialFactorial(n, n - r + 1);
denominator = factorial(r);
} else {
numerator = partialFactorial(n, r + 1);
denominator = factorial(n - r);
}
return numerator / denominator;
}
You can cut the nCr2 down, but the variables are there for explicitness. Basically, it just cancels out terms. Let's say you have 10C4. If you were doing it on paper, you'd simplify it as so:
10! / ((10 - 4)! * 4!)
10! / (6! * 4!)
10 * 9 * 8 * 7 * 6 ... * 1 / (6 * 5 * 4... * 1 * 4!)
10 * 9 * 8 * 7 *
6 ... * 1 / (
6 * 5 * 4... * 1 * 4!)
10 * 9 * 8 * 7 / 4!
To get the most out of it, you'll want to cancel the denominator factorial that is largest. In the case above, it is (n - r)! = (10 - 4)! = 6!. However, there are cases where r is greater than (n - r), so you'll want to cancel out r! instead. That is what the function determines.
If you want to support even larger numbers, you can perform even more divisions by first figuring out what else can cancel. For example, in this:
(10 * 9 * 8 * 7) / (4 * 3 * 2 * 1)
You can cancel out the 4, 3, 2:
(5 * 3 * 2 * 7) = 210
That would require some extra work though. I didn't include that.
Good luck! Btw, my code is in Java. You might have to rewrite a bit of it to fit C#, but the syntax of our codes are pretty similar so it shouldn't be a problem. I tested it versus the regular nCr (in your first post), and it indeed allowed me to calculate some larger factorials e.g. 22 choose 15.
P.S. There may be other ways of going about it. I just went with what came to mind.
