Combinatoric и выбирают R' в математике Java?

Математическая формула для этого:

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

Не должно быть трудно понять это оттуда :)

Я просто пытаюсь вычислить количество 2-х комбинаций карт с разными размерами колоды....

Нет необходимости импортировать внешнюю библиотеку - из определения комбинации, с карточками n, которые были бы n*(n-1)/2

Бонусный вопрос: Эта же самая формула вычисляет сумму первых n-1 целых чисел - вы понимаете, почему они одинаковые? :)

binomialCoefficient , в Commons Math

Рекурсивное определение дает вам довольно простую функцию выбора, которая отлично работает для небольших значений. Если вы планируете использовать этот метод часто или с большими значениями, было бы неплохо запоминать его, но в остальном все работает нормально.

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

Улучшение времени выполнения этой функции оставлено как упражнение для читателя :)

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

В этой формуле можно многое отменить, поэтому обычно факториалы не представляют проблемы. Допустим, R > (N-R), тогда отмените N!/R! до (R+1) * (R+2) * ... * N. Правда, int очень ограничен (около 13!).

Но тогда можно было бы с каждой итерацией еще и делить. В псевдокоде:

d := 1
r := 1

m := max(R, N-R)+1
for (; m <= N; m++, d++ ) {
    r *= m
    r /= d
}

Важно начинать деление с единицы, хотя это кажется излишним. Но приведем пример:

for N = 6, R = 2: 6!/(2!*4!) => 5*6/(1*2)

Если мы оставим 1, то вычислим 5/2*6. Деление вышло бы из области целых чисел. Оставляя 1, мы гарантируем, что этого не произойдет, поскольку ни первый, ни второй операнд умножения четный.

По той же причине мы не используем r *= (m/d).

Всё это можно пересмотреть

r := max(R, N-R)+1
for (m := r+1,d := 2; m <= N; m++, d++ ) {
    r *= m
    r /= d
}

Формула

На самом деле очень легко вычислить N выбрать K, даже не вычисляя факториалы.

Мы знаем, что формула для (N выбирает K) имеет вид:

    N!
 --------
 (N-K)!K!

Поэтому формула для (N выбирает K+1) имеет вид:

       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)

То есть:

(N choose K+1) = (N choose K) * (N-K)/(K+1)

Мы также знаем, что (N выбирает 0) имеет вид:

 N!
---- = 1
N!0!

Это дает нам легкую отправную точку, и, используя приведенную выше формулу, мы можем найти (N выбирает K) для любого K > 0 с K умножения и K деления.

Простой треугольник Паскаля

Сложив все вышесказанное вместе, мы можем легко составить треугольник Паскаля следующим образом:

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

Выводится:

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 версия

Применение формулы для BigInteger просто:

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"

Согласно Google, 133 выбираем 71 = 5.55687037 × 10³⁸.

References

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