blocks|key|1123622|text|其数学公式为：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1123623|N!/((R!)(N-R)!)|code-block|syntax|javascript|1123624|从那里应该不难弄清楚:)|1123625|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

The mathematical formula for this is:

<pre><code>N!/((R!)(N-R)!)
</code></pre>

Shouldn't be hard to figure it out from there :)

blocks|key|1123669|text|apache-commons+"Math“在org.apache.commons.math4.util.CombinatoricsUtils中支持这一点|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1123670|entityMap|0|LINK|mutability|MUTABLE|url|http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math4/util/CombinatoricsUtils.html#binomialCoefficient-int-int-^0|M|1C|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

The apache-commons "Math" supports this in
<a href="http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math4/util/CombinatoricsUtils.html#binomialCoefficient-int-int-" rel="noreferrer">org.apache.commons.math4.util.CombinatoricsUtils</a>

blocks|key|1338712|text|binomialCoefficient，在Commons+Math中|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1338713|entityMap|0|LINK|mutability|MUTABLE|url|http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/util/ArithmeticUtils.html#binomialCoefficient(int,%2520int))|1|http://commons.apache.org/math/^0|0|J|0|J|0|L|C|1|0^^$0|@$1|2|3|4|5|6|7|P|8|@$9|Q|A|R|B|C]]|D|@$9|S|A|T|1|U]|$9|V|A|W|1|X]]|E|$]]|$1|F|3|-4|5|6|7|Y|8|@]|D|@]|E|$]]]|G|$H|$5|I|J|K|E|$L|M]]|N|$5|I|J|K|E|$L|O]]]]

<a href="http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/util/ArithmeticUtils.html#binomialCoefficient(int,%20int)" rel="nofollow noreferrer"><code>binomialCoefficient</code></a>, in <a href="http://commons.apache.org/math/" rel="nofollow noreferrer">Commons Math</a>

blocks|key|1123819|text|recursive+definition提供了一个非常简单的选择函数，它可以很好地处理较小的值。如果您计划多次运行此方法，或者对较大的值执行此操作，那么将其记入内存将是值得的，但除此之外，它可以很好地工作。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1123820|public+static+long+choose(long+total,+long+choose){
++++if(total+<+choose)
++++++++return+0;
++++if(choose+==+0+%7C%7C+choose+==+total)
++++++++return+1;
++++return+choose(total-1,choose-1)%2Bchoose(total-1,choose);
}|code-block|syntax|javascript|1123821|改进此函数的运行时将作为一个exercise+for+the+reader+:)|1123822|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Binomial_coefficient#Recursive_definition|1|http://en.wikipedia.org/wiki/Memoization^0|0|K|0|0|0|E|N|1|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@$A|V|B|W|1|X]]|C|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|Z|8|@]|9|@$A|10|B|11|1|12]]|C|$]]|$1|K|3|-4|5|6|7|13|8|@]|9|@]|C|$]]]|L|$M|$5|N|O|P|C|$Q|R]]|S|$5|N|O|P|C|$Q|T]]]]

The <a href="http://en.wikipedia.org/wiki/Binomial_coefficient#Recursive_definition" rel="noreferrer">recursive definition</a> gives 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.

<pre><code>public static long choose(long total, long choose){
 if(total &lt; choose)
 return 0;
 if(choose == 0 || choose == total)
 return 1;
 return choose(total-1,choose-1)+choose(total-1,choose);
}
</code></pre>

Improving the runtime of this function is left as an <a href="http://en.wikipedia.org/wiki/Memoization" rel="noreferrer">exercise for the reader</a> :)

blocks|key|1123845|text|guava有IntMath#binomial(int,+int)、LongMath#binomial(int,+int)和BigIntegerMath#binomial(int,+int)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1123846|entityMap|0|LINK|mutability|MUTABLE|url|http://code.google.com/p/guava-libraries/|1|http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/math/IntMath.html#binomial%2528int,%2520int%2529|2|http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/math/LongMath.html#binomial%2528int,%2520int%2529|3|http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/math/BigIntegerMath.html#binomial%2528int,%2520int%2529^0|0|5|0|6|Q|1|X|R|2|1P|X|3|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@$A|S|B|T|1|U]|$A|V|B|W|1|X]|$A|Y|B|Z|1|10]|$A|11|B|12|1|13]]|C|$]]|$1|D|3|-4|5|6|7|14|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]|N|$5|G|H|I|C|$J|O]]|P|$5|G|H|I|C|$J|Q]]]]

<a href="http://code.google.com/p/guava-libraries/" rel="nofollow">guava</a> has <a href="http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/math/IntMath.html#binomial%28int,%20int%29" rel="nofollow">IntMath#binomial(int, int)</a>, <a href="http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/math/LongMath.html#binomial%28int,%20int%29" rel="nofollow">LongMath#binomial(int, int)</a> and <a href="http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/math/BigIntegerMath.html#binomial%28int,%20int%29" rel="nofollow">BigIntegerMath#binomial(int, int)</a>.

blocks|key|1123884|text|ArithmeticUtils.factorial显然已经被弃用了。请尝试CombinatoricsUtils.binomialCoefficientDouble(n,r)|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1123885|entityMap^0|0|P|11|1D|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|M|8|@]|D|@]|E|$]]]|G|$]]

<code>ArithmeticUtils.factorial</code> is apparently deprecated now. Please try <code>CombinatoricsUtils.binomialCoefficientDouble(n,r)</code>

blocks|key|1338944|text|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)!
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1338945|从几年前我所做的答案中编辑，其中a，b和c是整数，整数溢出使该方法严重不可用。这个在可靠性方面并不是很好，但它是懒惰的。|unstyled|1338946|如果值超过了long的限制，这也将成为砖块。不太可行，除非你试图为学校的项目或其他东西找到一些快速的解决方案。|1338947|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|L|8|@]|9|@]|A|$]]|$1|G|3|H|5|F|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|F|7|N|8|@]|9|@]|A|$]]]|J|$]]

<pre><code>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 &gt; 0; o--) { a = a * o; }
 for (int o = (int)b - 1; o &gt; 0; o--) { b = b * o; }
 for (int o = (int)c - 1; o &gt; 0; o--) { c = c * o; }

 return (a / (b * c)); // n! / r! * (n - r)!
}
</code></pre>

Edited from answer I made few years back, where a, b, and c were ints and integer overflow made the method critically unusable. This one is not really any better in terms of reliability, but it's lazy.

This will brick as well, if the value goes over long's limit... Not very feasible unless you're trying to find some quick solution for a school project or something.

blocks|key|1124073|text|与芭乐版本类似，还有一个由Richard+J.Mathar称为org.nevec.rjm的BigIntegerMath类here，它是类的包。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1124074|它们的实现为二项式方法提供了两个签名:+int，int和BigInteger，BigInteger。|1124075|entityMap|0|LINK|mutability|MUTABLE|url|http://arxiv.org/src/0908.3030v2/anc^0|1O|4|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

Similar to the guava version, there is a BigIntegerMath class <a href="http://arxiv.org/src/0908.3030v2/anc" rel="nofollow">here</a> by Richard J. Mathar refered to as org.nevec.rjm, which is the package of the classes. 

Their implementation provides two signatures for the binomial method: int,int and BigInteger,BigInteger.

blocks|key|1124131|text|使用hashmap改进@dimo414的解决方案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1124132|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+%7C%7C+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)%2Bchoose(total-1,choose));
++++}
++++return+map.get(total).get(choose);
}|code-block|syntax|javascript|1124133|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Using a hashmap to improve @dimo414 's solution:

<pre><code>private static Map&lt;Integer, Map&lt;Integer, Integer&gt;&gt; map = new HashMap&lt;&gt;();
private static int choose(int total, int choose){
 if(total &lt; choose)
 return 0;
 if(choose == 0 || choose == total)
 return 1;

 if (! (map.containsKey(total) &amp;&amp; map.get(total).containsKey(choose))){
 map.put(total, new HashMap&lt;&gt;());
 map.get(total).put(choose, choose(total-1,choose-1)+choose(total-1,choose));
 }
 return map.get(total).get(choose);
}
</code></pre>

blocks|key|1339153|text|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%2B%2B)
++++++++++++combinationNcK(inputList.subList(i+%2B+1,+inputList.size()),+prefix+%2B+","+%2B+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);
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1339154|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>public static void combinationNcK(List&lt;String&gt; inputList, String prefix, int chooseCount, List&lt;String&gt; resultList) {
 if (chooseCount == 0)
 resultList.add(prefix);
 else {
 for (int i = 0; i &lt; 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-&gt;str.substring(1)).forEach(System.out::println);
 }
 }
}

public static void main(String[] args) {
 List&lt;String&gt; positions = Arrays.asList(new String[] { "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12" });
 List&lt;String&gt; resultList = new ArrayList&lt;String&gt;();
 combinationNcK(positions, "", 3, resultList);
}
</code></pre>

blocks|key|1339239|text|我们也可以利用以下事实，而不是递归地实现n+slow+k(对于大数字，这可能会变得很慢)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1339240|++++++++++++++++n(n-1)(n-2)...(n-k%2B1)
++n+choose+k+=++--------------------
++++++++++++++++++++++++k!|code-block|syntax|javascript|1339241|我们仍然需要计算k!，但这可以比递归方法快得多。|1339242|private+static+long+choose(long+n,+long+k)+{
++++long+numerator+=+1;
++++long+denominator+=+1;

++++for+(long+i+=+n;+i+>=+(n+-+k+%2B+1);+i--)+{
++++++++numerator+*=+i;
++++}

++++for+(long+i+=+k;+i+>=+1;+i--)+{
++++++++denominator+*=+i;
++++}

++++return+(numerator+/+denominator);
}|1339243|请注意，上面的choose方法假设n和k都不是负的。此外，对于足够大的值，long数据类型可能会溢出。如果结果正确，则应使用BigInteger版本。分子和/或分母应超过64位。|1339244|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|S|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

Instead of implementing n choose k recursively (which can get slow with large numbers), we can also make use of the fact that:

<pre><code> n(n-1)(n-2)...(n-k+1)
 n choose k = --------------------
 k!
</code></pre>

We still need to calculate k!, but this can be done much faster than the recursive method.

<pre><code>private static long choose(long n, long k) {
 long numerator = 1;
 long denominator = 1;

 for (long i = n; i &gt;= (n - k + 1); i--) {
 numerator *= i;
 }

 for (long i = k; i &gt;= 1; i--) {
 denominator *= i;
 }

 return (numerator / denominator);
}
</code></pre>

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.

Is there a built in method in a java library that can compute 'N choose R' for any N, R?

Combinatoric 'N choose R' in java math?

在java库中有没有一个内置的方法，可以为任何N，R计算'N choose R‘？

问java数学中的组合式'N choose‘？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问java数学中的组合式'N choose‘？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问java数学中的组合式'N choose‘？
EN