Che cosa è un buon modo per implementare scegliere la notazione in Java?

Question

... preferibilmente in Java. Ecco quello che ho:

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

Mi chiedo se c'è un modo migliore di fare questo?

Answer 1

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

Si potrebbe fare qualcosa di simile a 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;
}

Modifica Se x e y sono grandi, si traboccherà più lentamente (vale a dire, essere sicuro per valori più grandi di X & Y) se si divide la vostra risposta come si va avanti:

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

Answer 2

I numeri avete a che fare con diventeranno abbastanza grande e supereranno rapidamente la precisione dei valori double, dando i risultati inaspettatamente sbagliate. Per questo motivo si può prendere in considerazione una soluzione precisione arbitraria come l'utilizzo di java.math.BigInteger, che non soffrono di questo problema.

Answer 3

Quello che devi sembra piuttosto chiaro per me, ad essere onesti. Certo avevo messo le dichiarazioni di ritorno in parentesi come quella è la convenzione seguo, ma a parte che sembra circa buono come si arriva.

Credo che avrei probabilmente invertire l'ordine del secondo ciclo, in modo che entrambi i loop sono ascendenti.

Come dice Greg, se avete bisogno di ottenere risposte precise per i grandi numeri, si dovrebbe prendere in considerazione i tipi di dati alternativi. Dato che il risultato dovrebbe sempre essere un numero intero, si potrebbe desiderare di prendere BigInteger (nonostante tutte le divisioni, il risultato sarà sempre un numero intero):

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

ho codificato questo in C #, ma ho cercato di renderlo il più applicabile possibile per Java.

Derivato da alcune di queste fonti, oltre ad un paio di piccole cose da me.

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

Codice:

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

per

  

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

utilizzare questo (pseudocodice)

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

Questa versione non richiede BigInteger o aritmetica in virgola mobile e funziona senza errori di overflow per tutti n meno di 62. 62 sopra 28 è la prima coppia di provocare un overflow.

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

Il seguente test dimostra che questo è vero:

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