在Javamath组合'NselectR'?

有一个Java库中的内置方法,可以计算'NselectR'的任何N,R?

apache-commons “Math”支持: Math3.Utils.CombinatoricsUtils

公式

计算N choose K实际上非常容易,甚至不需要计算因子。

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

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

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

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

那是:

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

我们也知道(N choose 0)是:

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

所以这给了我们一个简单的起点,并且使用上面的公式,我们可以find(N choose K)任何K > 0K乘法和K分割。


易帕斯卡的三angular形

综合上述,我们可以很容易地生成帕斯卡三angular形如下:

  for (int n = 0; n < 10; n++) { int nCk = 1; for (int k = 0; k <= n; k++) { System.out.print(nCk + " "); nCk = nCk * (nk) / (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(Nk)) .divide(BigInteger.valueOf(k+1)); } return ret; } //... System.out.println(binomial(133, 71)); // prints "555687036928510235891585199545206017600" 

据谷歌133选71 = 5.55687037×10 38


参考

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

recursion定义给你一个非常简单的select函数,它可以很好地处理小值。 如果你正在计划运行这个方法很多,或者大的值,它会支付memoize它,但其他方面工作得很好。

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

改善这个function的运行时间是读者的一个练习 🙂

我只是试图计算不同套牌大小的2张牌组合的数量…

不需要从组合的定义中导入一个外部库,其中n将是n*(n-1)/2

奖金问题:这个公式计算出前n-1整数的总和 – 你知道他们为什么一样吗? 🙂

这个math公式是:

 N!/((R!)(NR)!) 

不应该很难从中找出:)

N!/((R 1)(NR)!)

在这个公式中有很多你可以取消,所以通常因子没有问题。 假设R>(NR)然后取消N!/ R! 到(R + 1)*(R + 2)* … * N.但是真的,int是非常有限的(大约13!)。

但是,每一次迭代都可以分开。 在伪代码中:

 d := 1 r := 1 m := max(R, NR)+1 for (; m <= N; m++, d++ ) { r *= m r /= d } 

尽pipe这看起来是多余的,但开始一个分区是很重要的。 但让我们举个例子吧:

 for N = 6, R = 2: 6!/(2!*4!) => 5*6/(1*2) 

如果我们离开1,我们会计算5/2 * 6。 该部门将离开整数域。 离开1我们保证我们不这样做,因为乘法的第一或第二操作数是偶数。

出于同样的原因,我们不使用r *= (m/d)

整个事情可以修改为

 r := max(R, NR)+1 for (m := r+1,d := 2; m <= N; m++, d++ ) { r *= m r /= d } 

binomialCoefficient ,在Commons Math中

下面的例程将使用recursion定义和memoization来计算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; } 

guava有IntMath#binomial(int,int) , LongMath#binomial(int,int)和BigIntegerMath#binomial(int,int) 。

ArithmeticUtils.factorial现在显然已被弃用。 请尝试CombinatoricsUtils.binomialCoefficientDouble(n,r)

类似于番石榴版本,Richard J. Mathar 在这里有一个BigIntegerMath类,被称为org.nevec.rjm,它是类的包。

它们的实现为二项式方法提供了两个签名:int,int和BigInteger,BigInteger。

使用hashmap来改进@ dimo414的解决scheme:

 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); } 
 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); } 
 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是整数,整数溢出使得这个方法严重无法使用。 这个在可靠性方面并不是很好,但是很懒。

如果价值超过长期的限制,这也将是砖头…除非你想为学校项目寻找一些快速解决scheme,否则不太可行。