java数学中的组合'N选择R'？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2201113/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Combinatoric 'N choose R' in java math?
提问by Aly
Is there a built in method in a java library that can compute 'N choose R' for any N, R?
java库中是否有内置方法可以为任何N，R计算“N选择R”？
采纳答案by theomega
The apache-commons "Math" supports this in org.apache.commons.math4.util.CombinatoricsUtils
apache-commons "Math" 在org.apache.commons.math4.util.CombinatoricsUtils 中支持这一点
回答by Aistina
The mathematical formula for this is:
其数学公式为：
N!/((R!)(N-R)!)
Shouldn't be hard to figure it out from there :)
从那里想出来应该不难:)
回答by Valentin Rocher
回答by BlueRaja - Danny Pflughoeft
I am just trying to calculate number of 2 card combinations with different deck sizes...
我只是想计算具有不同甲板大小的 2 张牌组合的数量...
No need to import an external library - from the definition of combination, with ncards that would be n*(n-1)/2
无需导入外部库 - 从组合的定义中，可以使用n卡片n*(n-1)/2
Bonus question:This same formula calculates the sum of the first n-1integers - do you see why they're the same? :)
额外问题：这个相同的公式计算第一个n-1整数的总和- 你明白为什么它们相同吗？:)
回答by dimo414
The recursive definitiongives you a pretty simple choose function which will work fine for small values. If you're planning on running this method a lot, or on large values, it would pay to memoize it, but otherwise works just fine.
该递归定义为您提供了一个非常简单的选择功能，将工作的优良小的值。如果您计划多次运行此方法，或在大值上运行此方法，则需要记住它，否则就可以正常工作。
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);
}
Improving the runtime of this function is left as an exercise for the reader:)
改进此函数的运行时间留给读者练习:)
回答by Ralph M. Rickenbach
N!/((R!)(N-R)!)
N!/((R!)(NR)!)
There is a lot you can cancel down in this formula, so usually the factorials are no problem. Let's say that R > (N-R) then cancel down N!/R! to (R+1) * (R+2) * ... * N. But true, int is very limited (around 13!).
在这个公式中有很多可以取消，所以通常阶乘没有问题。假设 R > (NR) 然后取消 N!/R! 到 (R+1) * (R+2) * ... * N。但是，int 非常有限（大约 13！）。
But then one could with each iteration also divide. In pseudocode:
但是，每个迭代也可以划分。在伪代码中：
d := 1
r := 1
m := max(R, N-R)+1
for (; m <= N; m++, d++ ) {
r *= m
r /= d
}
It is important to start the division with one, even though this seems to be superfluous. But let's make an example:
以一个开始划分很重要，即使这似乎是多余的。但让我们举个例子：
for N = 6, R = 2: 6!/(2!*4!) => 5*6/(1*2)
If we leave 1 out we would calculate 5/2*6. The division would leave the integer domain. Leaving 1 in we guarantee that we don't do that as either the first or second operand of the multiplication is even.
如果我们省略 1，我们将计算 5/2*6。除法将离开整数域。保留 1 我们保证我们不会这样做，因为乘法的第一个或第二个操作数是偶数。
For the same reason we do not use r *= (m/d).
出于同样的原因，我们不使用r *= (m/d).
The whole thing could be revised to
整个事情可以修改为
r := max(R, N-R)+1
for (m := r+1,d := 2; m <= N; m++, d++ ) {
r *= m
r /= d
}
回答by polygenelubricants
The Formula
公式
It's actually very easy to compute N choose Kwithout even computing factorials.
它实际上很容易计算N choose K，甚至不需要计算阶乘。
We know that the formula for (N choose K)is:
我们知道公式为(N choose K)：
N!
--------
(N-K)!K!
Therefore, the formula for (N choose K+1)is:
因此，公式为(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)
That is:
那是：
(N choose K+1) = (N choose K) * (N-K)/(K+1)
We also know that (N choose 0)is:
我们也知道(N choose 0)：
N!
---- = 1
N!0!
So this gives us an easy starting point, and using the formula above, we can find (N choose K)for any K > 0with Kmultiplications and Kdivisions.
所以这给了我们一个简单的出发点，并使用上面的公式，我们可以找到(N choose K)任何K > 0与K乘法和K部门。
Easy Pascal's Triangle
简单的帕斯卡三角形
Putting the above together, we can easily generate Pascal's triangle as follows:
综上所述，我们可以很容易地生成帕斯卡三角形如下：
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();
}
This prints:
这打印：
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
BigIntegerversion
BigInteger版本
Applying the formula for BigIntegeris straightforward:
应用公式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"
According to Google, 133 choose 71 = 5.55687037 × 1038.
根据谷歌，133 选择 71 = 5.55687037 × 10 38。
References
参考
回答by polygenelubricants
The following routine will compute the n-choose-k, using the recursive definition and memoization. The routine is extremelyfast and accurate:
以下例程将使用递归定义和记忆来计算 n-choose-k。该例程非常快速和准确：
inline unsigned long long n_choose_k(const unsigned long long& n,
const unsigned long long& k)
{
if (n < k) return 0;
if (0 == n) return 0;
if (0 == k) return 1;
if (n == k) return 1;
if (1 == k) return n;
typedef unsigned long long value_type;
value_type* table = new value_type[static_cast<std::size_t>(n * n)];
std::fill_n(table,n * n,0);
class n_choose_k_impl
{
public:
n_choose_k_impl(value_type* table,const value_type& dimension)
: table_(table),
dimension_(dimension)
{}
inline value_type& lookup(const value_type& n, const value_type& k)
{
return table_[dimension_ * n + k];
}
inline value_type compute(const value_type& n, const value_type& k)
{
if ((0 == k) || (k == n))
return 1;
value_type v1 = lookup(n - 1,k - 1);
if (0 == v1)
v1 = lookup(n - 1,k - 1) = compute(n - 1,k - 1);
value_type v2 = lookup(n - 1,k);
if (0 == v2)
v2 = lookup(n - 1,k) = compute(n - 1,k);
return v1 + v2;
}
value_type* table_;
value_type dimension_;
};
value_type result = n_choose_k_impl(table,n).compute(n,k);
delete [] table;
return result;
}
回答by Olivier Cailloux
回答by Kruti Rao Erraguntala
ArithmeticUtils.factorialis apparently deprecated now. Please try CombinatoricsUtils.binomialCoefficientDouble(n,r)
ArithmeticUtils.factorial现在显然已弃用。请尝试 CombinatoricsUtils.binomialCoefficientDouble(n,r)
