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

Question

... желательно на Яве. Вот что у меня есть:

//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

выберите (n,k) = n! / (нк)! к!

Вы можете сделать что-то подобное в 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

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

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

Как говорит Грег, если вам нужно получить точные ответы для больших чисел, вы должны рассмотреть альтернативные типы данных. Учитывая, что результат всегда должен быть целым числом, вы можете выбрать 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 3

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

Answer 4

За

N!/((R!)(NR)!)

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

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 5

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