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

EDIT 如果 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！）（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 6

此版本不需要 BigInteger 或浮点算术，并且对于小于 62 的所有 n 都不会出现溢出错误。超过 28 的 62 是第一对导致溢出的结果。

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