Qu'est-ce qu'un bon moyen de mettre en œuvre choisir la notation en Java?

Question

... de préférence en Java. Voici ce que j'ai:

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

Je me demande s'il y a une meilleure façon de le faire?

Answer 1

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

Vous pouvez faire quelque chose comme ça dans 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;
}

EDIT Si x et y sont grandes, vous débordera plus lentement (à savoir, être sans danger pour les plus grandes valeurs de x et y) si vous divisez votre réponse que vous progressez:

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

Answer 2

Les chiffres que vous traitez deviendront assez grandes et vont rapidement dépasser la précision des valeurs de double, vous donnant des résultats de façon inattendue faux. Pour cette raison, vous voudrez peut-être envisager une solution de précision arbitraire comme l'utilisation java.math.BigInteger, qui ne souffre pas de ce problème.

Answer 3

Qu'est-ce que vous avez l'air assez clair pour moi, pour être honnête. Il est vrai que je mettrais les déclarations de retour dans accolades qui est la convention que je suis, mais à part cela il semble à peu près aussi bon qu'il obtient.

Je pense que je serais probablement inverser l'ordre de la seconde boucle, de sorte que les deux boucles sont ascendantes.

Comme le dit Greg, si vous avez besoin d'obtenir des réponses précises pour un grand nombre, vous devriez considérer les types de données alternatives. Étant donné que le résultat doit toujours être un entier, vous voudrez peut-être choisir BigInteger (malgré toutes les divisions, le résultat sera toujours un entier):

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

Je Codé Ce en C #, mais j'ai essayé de le rendre aussi applicable que possible Java.

Dérivé de certaines de ces sources, ainsi que quelques petites choses de moi.

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

Code:

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

pour

  

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

Cette (pseudo-code)

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

Cette version ne nécessite pas BigInteger ou arithmétique à virgule flottante et fonctionne sans erreur de débordement pour tous n moins de 62. 62 plus de 28 est la première paire d'entraîner un débordement.

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

Le test suivant prouve que cela est vrai:

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