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

Question

...предпочтительно на Java.Вот что у меня есть:

//x choose y
public static double choose(int x, int y) {
    if (y < 0 || y > x) return 0;
    if (y == 0 || y == x) return 1;

    double answer = 1;
    for (int i = x-y+1; i <= x; i++) {
        answer = answer * i;
    }
    for (int j = y; j > 1; j--) {
        answer = answer / j;
    }
    return answer;
}

Мне интересно, есть ли лучший способ сделать это?

Answer 1

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;

Answer 2

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

Answer 3

Честно говоря, то, что у вас есть, выглядит для меня довольно ясно.По общему признанию, я бы заключил операторы 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;
}

Answer 4

Я закодировал это на 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;
}

Answer 5

для

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;

Answer 6

Эта версия не требует 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;
}