Combinatoric 'N choose R' in java math?
https://stackoverflow.com/questions/2201113
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Is there a built in method in a java library that can compute 'N choose R' for any N, R?
Solution
The apache-commons "Math" supports this in org.apache.commons.math4.util.CombinatoricsUtils
OTHER TIPS
The Formula
It's actually very easy to compute N choose K without even computing factorials.
We know that the formula for (N choose K) is:
N!
--------
(N-K)!K!
Therefore, the formula for (N choose K+1) is:
N! N! N! N! (N-K)
---------------- = --------------- = -------------------- = -------- x -----
(N-(K+1))!(K+1)! (N-K-1)! (K+1)! (N-K)!/(N-K) K!(K+1) (N-K)!K! (K+1)
That is:
(N choose K+1) = (N choose K) * (N-K)/(K+1)
We also know that (N choose 0) is:
N!
---- = 1
N!0!
So this gives us an easy starting point, and using the formula above, we can find (N choose K) for any K > 0 with K multiplications and K divisions.
Easy Pascal's Triangle
Putting the above together, we can easily generate Pascal's triangle as follows:
for (int n = 0; n < 10; n++) {
int nCk = 1;
for (int k = 0; k <= n; k++) {
System.out.print(nCk + " ");
nCk = nCk * (n-k) / (k+1);
}
System.out.println();
}
This prints:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
BigInteger version
Applying the formula for BigInteger is straightforward:
static BigInteger binomial(final int N, final int K) {
BigInteger ret = BigInteger.ONE;
for (int k = 0; k < K; k++) {
ret = ret.multiply(BigInteger.valueOf(N-k))
.divide(BigInteger.valueOf(k+1));
}
return ret;
}
//...
System.out.println(binomial(133, 71));
// prints "555687036928510235891585199545206017600"
According to Google, 133 choose 71 = 5.55687037 × 1038.
References
The recursive definition gives you a pretty simple choose function which will work fine for small values. If you're planning on running this method a lot, or on large values, it would pay to memoize it, but otherwise works just fine.
public static long choose(long total, long choose){
if(total < choose)
return 0;
if(choose == 0 || choose == total)
return 1;
return choose(total-1,choose-1)+choose(total-1,choose);
}
Improving the runtime of this function is left as an exercise for the reader :)
I am just trying to calculate number of 2 card combinations with different deck sizes...
No need to import an external library - from the definition of combination, with n cards that would be n*(n-1)/2
Bonus question: This same formula calculates the sum of the first n-1 integers - do you see why they're the same? :)
The mathematical formula for this is:
N!/((R!)(N-R)!)
Shouldn't be hard to figure it out from there :)
N!/((R!)(N-R)!)
There is a lot you can cancel down in this formula, so usually the factorials are no problem. Let's say that R > (N-R) then cancel down N!/R! to (R+1) * (R+2) * ... * N. But true, int is very limited (around 13!).
But then one could with each iteration also divide. In pseudocode:
d := 1
r := 1
m := max(R, N-R)+1
for (; m <= N; m++, d++ ) {
r *= m
r /= d
}
It is important to start the division with one, even though this seems to be superfluous. But let's make an example:
for N = 6, R = 2: 6!/(2!*4!) => 5*6/(1*2)
If we leave 1 out we would calculate 5/2*6. The division would leave the integer domain. Leaving 1 in we guarantee that we don't do that as either the first or second operand of the multiplication is even.
For the same reason we do not use r *= (m/d).
The whole thing could be revised to
r := max(R, N-R)+1
for (m := r+1,d := 2; m <= N; m++, d++ ) {
r *= m
r /= d
}
The following routine will compute the n-choose-k, using the recursive definition and memoization. The routine is extremely fast and accurate:
inline unsigned long long n_choose_k(const unsigned long long& n,
const unsigned long long& k)
{
if (n < k) return 0;
if (0 == n) return 0;
if (0 == k) return 1;
if (n == k) return 1;
if (1 == k) return n;
typedef unsigned long long value_type;
value_type* table = new value_type[static_cast<std::size_t>(n * n)];
std::fill_n(table,n * n,0);
class n_choose_k_impl
{
public:
n_choose_k_impl(value_type* table,const value_type& dimension)
: table_(table),
dimension_(dimension)
{}
inline value_type& lookup(const value_type& n, const value_type& k)
{
return table_[dimension_ * n + k];
}
inline value_type compute(const value_type& n, const value_type& k)
{
if ((0 == k) || (k == n))
return 1;
value_type v1 = lookup(n - 1,k - 1);
if (0 == v1)
v1 = lookup(n - 1,k - 1) = compute(n - 1,k - 1);
value_type v2 = lookup(n - 1,k);
if (0 == v2)
v2 = lookup(n - 1,k) = compute(n - 1,k);
return v1 + v2;
}
value_type* table_;
value_type dimension_;
};
value_type result = n_choose_k_impl(table,n).compute(n,k);
delete [] table;
return result;
}
ArithmeticUtils.factorial is apparently deprecated now. Please try CombinatoricsUtils.binomialCoefficientDouble(n,r)
Similar to the guava version, there is a BigIntegerMath class here by Richard J. Mathar refered to as org.nevec.rjm, which is the package of the classes.
Their implementation provides two signatures for the binomial method: int,int and BigInteger,BigInteger.
Using a hashmap to improve @dimo414 's solution:
private static Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
private static int choose(int total, int choose){
if(total < choose)
return 0;
if(choose == 0 || choose == total)
return 1;
if (! (map.containsKey(total) && map.get(total).containsKey(choose))){
map.put(total, new HashMap<>());
map.get(total).put(choose, choose(total-1,choose-1)+choose(total-1,choose));
}
return map.get(total).get(choose);
}
public static void combinationNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
if (chooseCount == 0)
resultList.add(prefix);
else {
for (int i = 0; i < inputList.size(); i++)
combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);
// Finally print once all combinations are done
if(prefix.equalsIgnoreCase("")){
resultList.stream().map(str->str.substring(1)).forEach(System.out::println);
}
}
}
public static void main(String[] args) {
List<String> positions = Arrays.asList(new String[] { "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12" });
List<String> resultList = new ArrayList<String>();
combinationNcK(positions, "", 3, resultList);
}
As per the formula: n!/ ((n-k)! * k!) If we simply compute numerator and denominator, many computations will be wasted and probably the range of "int", "float" or even "BigInteger" can fill. Thus, to overcome this scenario, we can cancel out the things before even multiplying the values.
suppose n=6, k=3
which is => 6*5*4*3*2*1 / ((3*2) * (3*2))
suppose if we multiply the numerator, the range can fill. Better option is to cancel it out before even multiplying the values.
In this case--> if we cancel out everything we are just left with: (2*5*2)
multiplying these values are far easier and will require less computation.
======================================================
The below mentioned code will work "efficiently" for numbers where the:
- n == k
- k < n
- k == 0
- the difference between n and k is too huge, eg. n=1000, k=2
- k = n/2 (MOST TOUGHEST)
- Value of k is close to half of the value of n
Probably the code can be still improved.
BigInteger calculateCombination(int num, int k) {
if (num == k || k == 0)
return BigInteger.ONE ;
int numMinusK = num - k;
int stopAt; // if n=100, k=2 , can stop the multiplication process at 100*99
int denominator;
// if n=100, k=98 OR n=100, k=2 --> output remains same.
// thus choosing the smaller number to multiply with
if (numMinusK > k) {
stopAt = numMinusK;
denominator = k;
} else {
stopAt = k;
denominator = numMinusK;
}
// adding all the denominator nums into list
List<Integer> denoFactList = new ArrayList<Integer>();
for (int i = 2; i <= denominator; i++) {
denoFactList.add(i);
}
// creating multiples list, because 42 / 27 is not possible
// but 42 / 3 and followed by 42 / 2 is also possible
// leaving us only with "7"
List<Integer> multiplesList = breakInMultiples(denoFactList);
Collections.sort(multiplesList, Collections.reverseOrder());
Iterator<Integer> itr;
BigInteger total = BigInteger.ONE;
while (num > 0 && num > stopAt) {
long numToMultiplyWith = num;
if (!multiplesList.isEmpty()) {
itr = multiplesList.iterator();
while (itr.hasNext()) {
int val = itr.next();
if (numToMultiplyWith % val == 0) {
numToMultiplyWith = numToMultiplyWith / val;
itr.remove();
}
}
}
total = total.multiply(BigInteger.valueOf(numToMultiplyWith));
num--;
}
return total;
}
ArrayList<Integer> breakInMultiples(List<Integer> denoFactList) {
ArrayList<Integer> multiplesList = new ArrayList<>();
for (int i : denoFactList)
updateListWithMultiplesOf(multiplesList, i);
return multiplesList;
}
void updateListWithMultiplesOf(ArrayList<Integer> list, int i) {
int count = 2;
while (i > 1) {
while (i % count == 0) {
list.add(count);
i = i / count;
}
count++;
}
}
Already there are a lots of solutions submitted.
Some solution didn't consider integer overflow.
Some solution calculated all possible nCr while given n and r. Result is more time and space needed.
In most cases we need to calculate nCr directly. I am going to share one more solution.
static long gcd(long a, long b) {
if (a == 0) return b;
return gcd(b%a, a);
}
// Compute (a^n) % m
static long bigMod(long a, long n, long m) {
if (n == 0) return 1;
if (n == 1) return a % m;
long ret = bigMod(a, n/2, m);
ret = (ret * ret) % m;
if (n % 2 == 1) return (ret * a) % m;
return ret;
}
// Function to find (1/a mod m).
// This function can find mod inverse if m are prime
static long modInverseFarmetsTheorem(long a, long m) {
if (gcd(a, m) != 1) return -1;
return bigMod(a, m-2, m);
}
// This function finds ncr using modular multiplicative inverse
static long ncr(long n, long r, long m) {
if (n == r) return 1;
if (r == 1) return n;
long start = n - Math.max(r, n - r) + 1;
long ret = 1;
for (long i = start; i <= n; i++) ret = (ret * i) % m;
long until = Math.min(r, n - r), denom = 1;
for (long i = 1; i <= until; i++) denom = (denom * i) % m;
ret = (ret * modInverseFarmetsTheorem(denom, m)) % m;
return ret;
}
Instead of implementing n choose k recursively (which can get slow with large numbers), we can also make use of the fact that:
n(n-1)(n-2)...(n-k+1)
n choose k = --------------------
k!
We still need to calculate k!, but this can be done much faster than the recursive method.
private static long choose(long n, long k) {
long numerator = 1;
long denominator = 1;
for (long i = n; i >= (n - k + 1); i--) {
numerator *= i;
}
for (long i = k; i >= 1; i--) {
denominator *= i;
}
return (numerator / denominator);
}
Be aware that the choose method above assumes that neither n nor k is negative. Also, the long data type can overflow for large enough values. A BigInteger version should be used if the result resp. numerator and/or denominator are expected to exceed 64 bits.
public static long nCr(int n, int r) {
long a = n;
long b = r;
long c = (n - r);
for (int o = (int)a - 1; o > 0; o--) { a = a * o; }
for (int o = (int)b - 1; o > 0; o--) { b = b * o; }
for (int o = (int)c - 1; o > 0; o--) { c = c * o; }
return (a / (b * c)); // n! / r! * (n - r)!
}
Edited from answer I made few years back, where a, b, and c were ints and integer overflow made the method critically unusable. This one is not really any better in terms of reliability, but it's lazy.
This will brick as well, if the value goes over long's limit... Not very feasible unless you're trying to find some quick solution for a school project or something.
