Каков хороший способ реализовать нотацию выбора в Java?

choose(n,k) = n! / (n-k)! k!

Вы можете сделать что-то подобное в O (k):

public static double choose(int x, int y) {
    if (y < 0 || y > x) return 0;
    if (y > x/2) {
        // choose(n,k) == choose(n,n-k), 
        // so this could save a little effort
        y = x - y;
    }

    double denominator = 1.0, numerator = 1.0;
    for (int i = 1; i <= y; i++) {
        denominator *= i;
        numerator *= (x + 1 - i);
    }
    return numerator / denominator;
}

ИЗМЕНИТЬ Если x и y большие, вы будете переполняться медленнее (т. е. быть в безопасности для больших значений x и y), если вы разделите свой ответ по мере продвижения:

    double answer = 1.0;
    for (int i = 1; i <= y; i++) {
        answer *= (x + 1 - i);
        answer /= i;           // humor 280z80
    }
    return answer;

Числа, с которыми вы имеете дело, станут довольно большими и быстро превысят точность значений double, что даст вам неожиданно неправильные результаты. По этой причине вы можете рассмотреть решение с произвольной точностью, такое как использование java.math.BigInteger, которое не будет страдать от этой проблемы.

То, что у вас есть, кажется мне довольно ясным, если честно. По общему признанию, я бы поместил операторы return в фигурные скобки, поскольку это соглашение, которому я следую, но кроме этого оно выглядит так же хорошо, как и получается.

Я думаю, что я бы, вероятно, изменил порядок второго цикла, чтобы оба цикла были восходящими.

Как говорит Грег, если вам нужно получить точные ответы для больших чисел, вам следует рассмотреть альтернативные типы данных. Учитывая, что результатом всегда должно быть целое число, вы можете выбрать BigInteger (несмотря на все деления, результатом всегда будет целое число):

public static BigInteger choose(int x, int y) {
    if (y < 0 || y > x) 
       return BigInteger.ZERO;
    if (y == 0 || y == x) 
       return BigInteger.ONE;

    BigInteger answer = BigInteger.ONE;
    for (int i = x - y + 1; i <= x; i++) {
        answer = answer.multiply(BigInteger.valueOf(i));
    }
    for (int j = 1; j <= y; j++) {
        answer = answer.divide(BigInteger.valueOf(j));
    }
    return answer;
}

Я закодировал это на C#, но я попытался сделать его как можно более применимым к Java.

Получено из некоторых из этих источников, плюс пара небольших вещей от меня.

• http://blog.plover.com/math/choose.html
• http://blog.plover.com/math/choose-2.html

Код:

public static long BinomialCoefficient(long n, long k)
{
    if (n / 2 < k)
        return BinomialCoefficient(n, n - k);

    if (k > n)
        return 0;

    if (k == 0)
        return 1;

    long result = n;
    for (long d = 2; d <= k; d++)
    {
        long gcd = (long)BigInteger.GreatestCommonDivisor(d, n);
        result *= (n / gcd);
        result /= (d / gcd);
        n++;
    }

    return result;
}

за

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

используйте это (псевдокод)

if (R>N) return 0;

long r = max(R, N-r)+1;
if (R==N) return 1;

for (long m = r+1, long d = 2; m <= N; m++, d++ ) {
    r *= m;
    r /= d;
}
return r;

Эта версия не требует BigInteger или арифметики с плавающей запятой и работает без ошибок переполнения для всех n меньше 62. 62 больше 28 — это первая пара, которая приводит к переполнению.

public static long nChooseK(int n, int k) {
    k = Math.min(k, n - k);

    if (n < 0 || k < 0)
        throw new IllegalArgumentException();

    if (k == 0)
        return 1;

    long value = n--;

    for (int i = 2; i <= k; i++) {
        value = Math.multiplyExact(value, n--);
        value /= i;
    }

    return value;
}

Следующий тест доказывает, что это так:

@Test
void nChooseKLongVsBigInt() {
    for (int n = 0; n < 62; n++) {
        for (int k = 0; k <= n; k++) {
            assertEquals(nChooseKBigInt(n, k), BigInteger.valueOf(nChooseK(n, k)));
        }
    }
}

private BigInteger nChooseKBigInt(int n, int k) {
    return factorial(n).divide(factorial(k).multiply(factorial(n - k)));
}

private BigInteger factorial(int number) {
    BigInteger result = BigInteger.ONE;

    for (int factor = 2; factor <= number; factor++) {
        result = result.multiply(BigInteger.valueOf(factor));
    }

    return result;
}