¿Qué es una buena manera de poner en práctica elegir la notación en Java?

Question

... preferentemente en Java. Aquí es lo que tengo:

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

Me pregunto si hay una mejor manera de hacer esto?

Answer 1

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

Se podría hacer algo como esto en 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;
}

Editar Si x y y son grandes, que se desbordará más lentamente (es decir, ser seguro para valores mayores de X & Y) si se divide la respuesta a medida que avanza:

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

Answer 2

Los números que está tratando llegarán a ser bastante grande y superará rápidamente la precisión de los valores double, dándole resultados inesperadamente equivocadas. Por esta razón es posible que desee considerar una solución de precisión arbitraria como el uso de java.math.BigInteger, que no sufren de este problema.

Answer 3

Lo que tienes parece bastante claro para mí, para ser honesto. Es cierto que me gustaría poner las declaraciones de retorno en los apoyos ya que es la convención sigo, pero aparte de eso, se ve casi tan bueno como se pone.

Creo que probablemente me invertir el orden del segundo bucle, de manera que ambos bucles son ascendentes.

Como dice Greg, si usted necesita para obtener respuestas precisas para grandes números, se debe tener en cuenta los tipos de datos alternativas. Teniendo en cuenta que el resultado siempre debe ser un número entero, es posible que desee elegir BigInteger (a pesar de todas las divisiones, el resultado será siempre un número entero):

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

codifiqué esto en C #, pero he intentado que sea lo más aplicable posible a Java.

Derivado de algunas de estas fuentes, además de un par pequeñas cosas de mí.

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

Código:

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

para

  

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

utilizar este (Pseudocódigo)

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

Esta versión no requiere BigInteger o la aritmética de punto flotante y funciona sin errores de desbordamiento para todos n menos de 62. 62 sobre 28 es el primer par para dar lugar a un desbordamiento.

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

La siguiente prueba demuestra que esto es cierto:

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