java库中是否有内置方法可以为任何N，R计算“N选择R”？
问问题
88478 次
17 回答
106
公式
它实际上很容易计算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除法。KK
易帕斯卡三角
综上所述，我们可以很容易地生成帕斯卡三角形如下：
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 38。
参考
于 2010-05-28T14:34:06.940 回答
49
apache-commons“数学”在 org.apache.commons.math4.util.CombinatoricsUtils中支持这一点
于 2010-02-04T16:06:14.053 回答
24
递归定义为您提供了一个非常简单的选择函数，该函数适用于小值。如果您计划大量运行此方法，或者在较大的值上运行，那么记住它是值得的，但除此之外就可以了。
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);
}
改进这个函数的运行时间留给读者练习:)
于 2010-02-10T09:01:58.327 回答
15
我只是想计算不同牌组大小的 2 张卡片组合的数量......
无需导入外部库 - 根据组合的定义，与n卡n*(n-1)/2
额外的问题： 这个相同的公式计算第一个n-1整数的总和 - 你明白为什么它们是相同的吗？:)
于 2010-02-05T14:48:12.313 回答
4
于 2010-02-04T16:06:38.527 回答
4
N!/((R!)(NR)!)
在这个公式中你可以取消很多，所以通常阶乘是没有问题的。假设 R > (NR) 然后取消 N!/R! 到 (R+1) * (R+2) * ... * N。但确实，int 非常有限（大约 13！）。
但是，每次迭代也可以划分。在伪代码中：
d := 1
r := 1
m := max(R, N-R)+1
for (; m <= N; m++, d++ ) {
r *= m
r /= d
}
从一个开始除法很重要，尽管这似乎是多余的。但是让我们举个例子：
for N = 6, R = 2: 6!/(2!*4!) => 5*6/(1*2)
如果我们省略 1，我们将计算 5/2*6。除法将离开整数域。保留 1 我们保证不会这样做，因为乘法的第一个或第二个操作数都是偶数。
出于同样的原因，我们不使用r *= (m/d).
整个事情可以修改为
r := max(R, N-R)+1
for (m := r+1,d := 2; m <= N; m++, d++ ) {
r *= m
r /= d
}
于 2010-05-28T12:07:51.213 回答
2
其数学公式为：
N!/((R!)(N-R)!)
从那里不应该很难弄清楚:)
于 2010-02-04T16:05:51.400 回答
2
以下例程将使用递归定义和记忆来计算 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;
}
于 2011-01-19T04:25:56.780 回答
1
于 2014-02-09T21:59:39.227 回答
1
ArithmeticUtils.factorial现在显然已弃用。请试试 CombinatoricsUtils.binomialCoefficientDouble(n,r)
于 2015-04-27T11:44:31.077 回答
0
与 guava 版本类似，Richard J. Mathar 在这里有一个 BigIntegerMath 类，称为 org.nevec.rjm，它是类的包。
他们的实现为二项式方法提供了两个签名：int,int 和 BigInteger,BigInteger。
于 2015-08-28T17:33:14.537 回答
0
使用 hashmap 改进 @dimo414 的解决方案：
private static Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
private static int choose(int total, int choose){
if(total < choose)
return 0;
if(choose == 0 || choose == total)
return 1;
if (! (map.containsKey(total) && map.get(total).containsKey(choose))){
map.put(total, new HashMap<>());
map.get(total).put(choose, choose(total-1,choose-1)+choose(total-1,choose));
}
return map.get(total).get(choose);
}
于 2016-10-29T18:27:24.487 回答
0
public static void combinationNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
if (chooseCount == 0)
resultList.add(prefix);
else {
for (int i = 0; i < inputList.size(); i++)
combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);
// Finally print once all combinations are done
if(prefix.equalsIgnoreCase("")){
resultList.stream().map(str->str.substring(1)).forEach(System.out::println);
}
}
}
public static void main(String[] args) {
List<String> positions = Arrays.asList(new String[] { "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12" });
List<String> resultList = new ArrayList<String>();
combinationNcK(positions, "", 3, resultList);
}
于 2016-12-04T07:45:23.833 回答
0
根据公式：n!/ ((nk)! * k!) 如果我们只计算分子和分母，会浪费很多计算，并且可能会填满 "int"、"float" 甚至 "BigInteger" 的范围。因此，为了克服这种情况，我们可以在乘以值之前取消这些东西。
假设n=6，k=3
即 => 6*5*4*3*2*1 / ((3*2) * (3*2))
假设如果我们乘以分子，范围可以填充。更好的选择是在乘以这些值之前将其取消。
在这种情况下——>如果我们取消剩下的所有内容：(2*5*2)
将这些值相乘要容易得多，并且需要更少的计算。
==================================================== ====
下面提到的代码将对以下数字“有效”地工作：
- n == k
- k < n
- k == 0
- n 和 k 之间的差异太大，例如。n=1000, k=2
- k = n/2（最艰难）
- k的值接近n值的一半
可能代码仍然可以改进。
BigInteger calculateCombination(int num, int k) {
if (num == k || k == 0)
return BigInteger.ONE ;
int numMinusK = num - k;
int stopAt; // if n=100, k=2 , can stop the multiplication process at 100*99
int denominator;
// if n=100, k=98 OR n=100, k=2 --> output remains same.
// thus choosing the smaller number to multiply with
if (numMinusK > k) {
stopAt = numMinusK;
denominator = k;
} else {
stopAt = k;
denominator = numMinusK;
}
// adding all the denominator nums into list
List<Integer> denoFactList = new ArrayList<Integer>();
for (int i = 2; i <= denominator; i++) {
denoFactList.add(i);
}
// creating multiples list, because 42 / 27 is not possible
// but 42 / 3 and followed by 42 / 2 is also possible
// leaving us only with "7"
List<Integer> multiplesList = breakInMultiples(denoFactList);
Collections.sort(multiplesList, Collections.reverseOrder());
Iterator<Integer> itr;
BigInteger total = BigInteger.ONE;
while (num > 0 && num > stopAt) {
long numToMultiplyWith = num;
if (!multiplesList.isEmpty()) {
itr = multiplesList.iterator();
while (itr.hasNext()) {
int val = itr.next();
if (numToMultiplyWith % val == 0) {
numToMultiplyWith = numToMultiplyWith / val;
itr.remove();
}
}
}
total = total.multiply(BigInteger.valueOf(numToMultiplyWith));
num--;
}
return total;
}
ArrayList<Integer> breakInMultiples(List<Integer> denoFactList) {
ArrayList<Integer> multiplesList = new ArrayList<>();
for (int i : denoFactList)
updateListWithMultiplesOf(multiplesList, i);
return multiplesList;
}
void updateListWithMultiplesOf(ArrayList<Integer> list, int i) {
int count = 2;
while (i > 1) {
while (i % count == 0) {
list.add(count);
i = i / count;
}
count++;
}
}
于 2018-03-28T19:54:04.060 回答
0
已经提交了很多解决方案。
一些解决方案没有考虑整数溢出。
一些解决方案在给定 n 和 r 时计算所有可能的 nCr。结果是需要更多的时间和空间。
在大多数情况下，我们需要直接计算 nCr。我将分享另一种解决方案。
static long gcd(long a, long b) {
if (a == 0) return b;
return gcd(b%a, a);
}
// Compute (a^n) % m
static long bigMod(long a, long n, long m) {
if (n == 0) return 1;
if (n == 1) return a % m;
long ret = bigMod(a, n/2, m);
ret = (ret * ret) % m;
if (n % 2 == 1) return (ret * a) % m;
return ret;
}
// Function to find (1/a mod m).
// This function can find mod inverse if m are prime
static long modInverseFarmetsTheorem(long a, long m) {
if (gcd(a, m) != 1) return -1;
return bigMod(a, m-2, m);
}
// This function finds ncr using modular multiplicative inverse
static long ncr(long n, long r, long m) {
if (n == r) return 1;
if (r == 1) return n;
long start = n - Math.max(r, n - r) + 1;
long ret = 1;
for (long i = start; i <= n; i++) ret = (ret * i) % m;
long until = Math.min(r, n - r), denom = 1;
for (long i = 1; i <= until; i++) denom = (denom * i) % m;
ret = (ret * modInverseFarmetsTheorem(denom, m)) % m;
return ret;
}
于 2018-11-12T02:09:03.940 回答
0
我们可以利用以下事实，而不是递归地实现 n 选择 k（这可能会变慢）：
n(n-1)(n-2)...(n-k+1)
n choose k = --------------------
k!
我们仍然需要计算 k!，但这可以比递归方法快得多。
private static long choose(long n, long k) {
long numerator = 1;
long denominator = 1;
for (long i = n; i >= (n - k + 1); i--) {
numerator *= i;
}
for (long i = k; i >= 1; i--) {
denominator *= i;
}
return (numerator / denominator);
}
Be aware that the choose method above assumes that neither n nor k is negative. Also, the long data type can overflow for large enough values. A BigInteger version should be used if the result resp. numerator and/or denominator are expected to exceed 64 bits.
于 2019-05-10T14:24:50.737 回答
-1
public static long nCr(int n, int r) {
long a = n;
long b = r;
long c = (n - r);
for (int o = (int)a - 1; o > 0; o--) { a = a * o; }
for (int o = (int)b - 1; o > 0; o--) { b = b * o; }
for (int o = (int)c - 1; o > 0; o--) { c = c * o; }
return (a / (b * c)); // n! / r! * (n - r)!
}
从几年前我所做的答案编辑，其中 a、b 和 c 是整数，整数溢出使该方法严重无法使用。就可靠性而言，这个并没有更好，但它很懒惰。
如果价值超过长期的限制，这也会变砖......除非你试图为学校项目或其他东西找到一些快速解决方案，否则这不是很可行。
于 2015-07-30T03:30:26.843 回答