What is the most efficient method to evaluate the value of "n choose k" ?
The brute force way I think would be to find n! / k! / (n-k)! by calculating each factorial separately.
A better strategy may be to use DP according to this recursive formula, nCk == (n-1)C(k-1) + (n-1)C(k). Is there any other better method to evaluate n choose k in terms of complexity and avoiding risk of overflow?
Here is my version, which works purely in integers (the division by k always produces an integer quotient) and is fast at O(k):
function choose(n, k)
if k == 0 return 1
return (n * choose(n - 1, k - 1)) / k
I wrote it recursively because it's so simple and pretty, but you could transform it to an iterative solution if you like.
You could use the Multiplicative formula for this:
http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula
Probably the easiest way to compute binomial coefficients (n choose k) without overflowing is to use Pascal's triangle. No fractions or multiplications are necessary. (n choose k). The nth row and kth entry of Pascal's triangle gives the value.
Take a look at this page. This is an O(n^2) operation with only addition, which you can solve with dynamic programming. It's going to be lightning fast for any number that can fit in a 64-bit integer.
If you're going to calculate many combinations like this, calculating the Pascal's Triangle is sure the best option. As you already know the recursive formula, I think I can past some code here:
MAX_N = 100
MAX_K = 100
C = [[1] + [0]*MAX_K for i in range(MAX_N+1)]
for i in range(1, MAX_N+1):
for j in range(1, MAX_K+1):
C[i][j] = C[i-1][j-1] + C[i-1][j];
print C[10][2]
print C[10][8]
print C[10][3]
After hitting a similar problem, I decided to compile the best solutions if have seen and run a simple test on each for a couple different values of n and k. I started with 10 or so functions and weeded out the ones that were just plain wrong or stopped working at specific values. Of all of the solutions, the answer above by user448810 is the cleanest and easiest to implement, I quite like it. Below will be code including each test i ran, the number of times i ean each function for each test, each functions code, the functions output and the time it took to get that output. I only did 20000 runs, there were still fluctuations in the time if i re ran the tests, but you should get a general sense of how well each worked.
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//EXPECTED VALUES
//x choose x = 1
//9 choose 4 =126
//52 choose 5 = 2598960;
//64 choose 33 = 1.777090076065542336E18;
//# of runs for each test: 20000
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//https://stackoverflow.com/a/12983878/4285191
public static double combination(long n, long k) {
double sum=0;
for(long i=0;i<k;i++) {
sum+=Math.Log10(n-i);
sum-=Math.Log10(i+1);
}
return Math.Pow(10, sum);
}
/*
10 choose 10
0.9999999999999992
Elapsed=00:00:00.0000015
9 choose 4
126.00000000000001
Elapsed=00:00:00.0000009
52 choose 5
2598959.9999999944
Elapsed=00:00:00.0000013
64 choose 33
1.7770900760655124E+18
Elapsed=00:00:00.0000058
*/
//........................................................
//https://stackoverflow.com/a/19125294/4285191
public static double BinomCoefficient(long n, long k) {
if (k > n) return 0;
if (n == k) return 1; // only one way to chose when n == k
if (k > n-k) k = n-k; // Everything is symmetric around n-k, so it is quicker to iterate over a smaller k than a larger one.
double c = 1;
for (long i = 1; i <= k; i++) {
c *= n--;
c /= i;
}
return c;
}
/*
10 choose 10
1
Elapsed=00:00:00
9 choose 4
126
Elapsed=00:00:00.0000001
52 choose 5
2598960
Elapsed=00:00:00.0000001
64 choose 33
1.7770900760655432E+18
Elapsed=00:00:00.0000006
*/
//........................................................
//https://stackoverflow.com/a/15302448/4285191
public static double choose(long n, long k) {
if (k == 0) return 1;
return (n * choose(n-1, k-1)) / k;
}
/*
10 choose 10
1
Elapsed=00:00:00.0000002
9 choose 4
126
Elapsed=00:00:00.0000003
52 choose 5
2598960
Elapsed=00:00:00.0000004
64 choose 33
1.777090076065543E+18
Elapsed=00:00:00.0000008
*/
//........................................................
//My own version which is just a mix of the two best above.
public static double binomialCoeff(int n, int k) {
if (k > n) return 0;
if (k > n-k) k = n-k; // Everything is symmetric around n-k, so it is quicker to iterate over a smaller k than a larger one.
double recusion(long n, long k) {
if (k == 0) return 1; // only one way to chose when n == k
return (n * recusion(n-1, k-1)) / k;
}
return recusion(n,k);
}
/*
10 choose 10
1
Elapsed=00:00:00
9 choose 4
126
Elapsed=00:00:00.0000001
52 choose 5
2598960
Elapsed=00:00:00.0000002
64 choose 33
1.777090076065543E+18
Elapsed=00:00:00.0000007
*/
//........................................................
//https://en.wikipedia.org/wiki/Binomial_coefficient
public static double binomial(long n, long k) {
// take advantage of symmetry
if (k > n-k) k = n-k;
long c = 1;
for (long i = 1; i <= k; i++, n--) {
// return 0 on potential overflow
if (c/i >= long.MaxValue/n) return 0;
// split c * n / i into (c / i * i) + (c % i * n / i)
c = (c / i * n) + (c % i * n / i);
}
return c;
}
/*
10 choose 10
1
Elapsed=00:00:00.0000006
9 choose 4
126
Elapsed=00:00:00.0000002
52 choose 5
2598960
Elapsed=00:00:00.0000003
64 choose 33
1.7770900760655424E+18
Elapsed=00:00:00.0000029
*/
If you have a lookup table of factorials then the calculation of C(n,k) will be very fast.
The problem with the n!/k!(n-k)! approach is not so much the cost as the issue with ! growing very rapidly so that, even for values of nCk which are well within the scope of, say, 64-bit integers, intermediate calculations are not. If you don't like kainaw's recursive addition approach you could try the multiplicative approach:
nCk == product(i=1..k) (n-(k-i))/i
where product(i=1..k) means the product of all the terms when i takes the values 1,2,...,k.
The fastest way is probably to use the formula, and not pascals triangle. Let's start not to do multiplications when we know that we're going to divide by the same number later. If k < n/2, let's have k = n - k. We know that C(n,k) = C(n,n-k) Now :
n! / (k! x (n-k)!) = (product of numbers between (k+1) and n) / (n-k)!
At least with this technique, you're never dividing by a number that you used to multiply before. You have (n-k) multiplications, and (n-k) divisions.
I'm thinking about a way to avoid all divisions, by finding GCDs between the numbers that we have to multiply, and those we have to divide. I'll try to edit later.
I haven't seen this answer before in case it helps someone else
def choose(n, k):
nominator = n
for i in range(1,k):
nominator *= (n-i)
k *= i
return nominator/k
Using recursive functions to solve this problem is not optimal in terms of space complexity. This is because recursive calls will build a call stack. I think it is possible to achieve the computation of n Choose k with k <= n in a linear time complexity and constant space complexity.
For 0 < k <= n, the maximum of n, k and n-k is n, therefore the idea is to only compute n! and to infer in the same loop, the values for k! and (n-k)!. Thus the final time complexity is O(n).
Such a function could look like this:
public static long combinationsCount(int n, int k) {
//this will hold the result for n!
long a = 1;
//this will hold the result for k!
long b = 1;
//this will hold the result for (n-k)!
long c = 1;
for (int i = 1; i <= n; i++) {
a *= i;
//if the current value of i is k, then a is equal to k!
if (i == k) {
b = a;
}
//if the current value of i is n-k, then a is equal to (n-k)!
if (i == n-k) {
c = a;
}
}
//n choose k formula
return a/(b*c);
}
Using Pascal's triangle is a fast method for calculating n choose k. You can refer to the answer here for more info.
The fastest method I know of would be to make use of the results from "On the Complexity of Calculating Factorials". Just calculate all 3 factorials, then perform the two division operations, each with complexity M(n logn).
Here is a very simple C++ implementation that minimizes the risk of overflow. You can also replace each long long with double to allow larger numbers at the cost of imprecise results.
long long combinations(int n, int k) {
long long product = 1;
for(int i = 1; i <= k; i++)
product = product*(n - k + i)/i; // Must do mul before div
return product;
}
The denominator will contain all the numbers from [1 .. k], while the numerator will contain all the numbers from [n - k + 1 .. n], noting that the first [1 .. n - k] factors are cancelled out by the (n - k)! factor on the denominator.
The order of how to perform these operations matter. It can be proven that (n - k + i) is divisible by i across all of the iteration steps, so none of the factors are off, as after i iterations, the numerator contains a product of i consecutive integers, which then implies the numerator is divisible by i.
"Most efficient" is a poor request. What are you trying to make efficient? The stack? Memory? Speed? Overall, my opinion is that the recursive method is most efficient because it only uses addition (a cheap operation) and the recursion won't be too bad for most cases. The function is:
nchoosek(n, k)
{
if(k==0) return 1;
if(n==0) return 0;
return nchoosek(n-1, k-1)+nchoosek(n-1,k);
}
