Combinatoric 'N choose R' in java math?

问题:

Is there a built in method in a java library that can compute 'N choose R' for any N, R?

回答1:

The apache-commons "Math" supports this in org.apache.commons.math4.util.CombinatoricsUtils

回答2:

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 × 10³⁸.

---

References

• Wikipedia/Binomial coefficient
• Wikipedia/Pascal's triangle
• Wikipedia/Combination

回答3:

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 :)

回答4:

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? :)

回答5:

The mathematical formula for this is:

N!/((R!)(N-R)!)

Shouldn't be hard to figure it out from there :)

回答6:

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
}

回答7:

binomialCoefficient, in Commons Math

回答8:

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;
}

回答9:

guava has IntMath#binomial(int, int), LongMath#binomial(int, int) and BigIntegerMath#binomial(int, int).

回答10:

ArithmeticUtils.factorial is apparently deprecated now. Please try CombinatoricsUtils.binomialCoefficientDouble(n,r)

回答11:

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.

回答12:

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);
}

回答13:

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);
}

回答14:

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:

1. n == k
2. k < n
3. k == 0
4. the difference between n and k is too huge, eg. n=1000, k=2
5. k = n/2 (MOST TOUGHEST)
6. 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++;
    }
}

回答15:

Already there are a lots of solutions submitted.

1. Some solution didn't consider integer overflow.

2. 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;
}

回答16:

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.