在Java数学中组合'N选择R'？

Question

在java库中是否有内置方法可以为任何N,R计算'N choose R'？

Answer 1

公式

N choose K即使没有计算因子,它实际上也很容易计算.

我们知道的公式(N choose K)是:

    N!
 --------
 (N-K)!K!

因此,公式为(N choose K+1):

       N!                N!                   N!               N!      (N-K)
---------------- = --------------- = -------------------- = -------- x -----
(N-(K+1))!(K+1)!   (N-K-1)! (K+1)!   (N-K)!/(N-K) K!(K+1)   (N-K)!K!   (K+1)

那是:

(N choose K+1) = (N choose K) * (N-K)/(K+1)

我们也知道(N choose 0):

 N!
---- = 1
N!0!

所以这给了我们一个简单的出发点,并使用上面的公式,我们可以找到(N choose K)任何K > 0与K乘法和K部门.

Easy Pascal的三角形

综合以上内容,我们可以轻松生成Pascal三角形,如下所示:

    for (int n = 0; n < 10; n++) {
        int nCk = 1;
        for (int k = 0; k <= n; k++) {
            System.out.print(nCk + " ");
            nCk = nCk * (n-k) / (k+1);
        }
        System.out.println();
    }

这打印:

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 

BigInteger 版

应用公式BigInteger很简单:

static BigInteger binomial(final int N, final int K) {
    BigInteger ret = BigInteger.ONE;
    for (int k = 0; k < K; k++) {
        ret = ret.multiply(BigInteger.valueOf(N-k))
                 .divide(BigInteger.valueOf(k+1));
    }
    return ret;
}

//...
System.out.println(binomial(133, 71));
// prints "555687036928510235891585199545206017600"

据谷歌称,133选择71 = 5.55687037×10 ³⁸.

参考

• 维基百科/二项式系数
• 维基百科/帕斯卡的三角形
• 维基百科/组合

Answer 2

apache-commons"Math"在org.apache.commons.math4.util.CombinatoricsUtils中支持这一点

Answer 3

该递归定义为您提供了一个非常简单的选择功能,将工作的优良小的值.如果您计划大量运行此方法,或者使用较大的值,则需要记住它,但是否则可以正常工作.

public static long choose(long total, long choose){
    if(total < choose)
        return 0;
    if(choose == 0 || choose == total)
        return 1;
    return choose(total-1,choose-1)+choose(total-1,choose);
}

改进这个函数的运行时间留给读者 :)

Answer 4

我只想计算不同甲板大小的2张牌组合的数量......

无需导入外部库 - 从组合的定义,可以使用n卡片n*(n-1)/2

额外问题: 这个相同的公式计算第一个n-1整数的总和- 你知道为什么它们是相同的吗？:)

Answer 5

binomialCoefficient，在公共数学中

返回二项式系数的精确表示，“n 选择 k”，即可以从 n 元素集中选择的 k 元素子集的数量。