Java中的组合数“N选R”在数学中如何表示？

Question

Java库中是否有内置方法可以计算任意N、R的组合数'C(N,R)'？

- Aly

---

如果结果溢出了int会怎样？这重要吗？你想要把结果作为BigInteger吗？ - Mark Byers

我只是在尝试计算不同牌堆大小（最多52张）的2张卡牌组合数量，因此不应超过1,326（52选2）。 - Aly

你知道52!等于80658175170943878571660636856403766975289505440883277824000000000000吗？因为根据你所接受的答案，你似乎没有考虑到该公式中涉及到的数字有多大。顺便提一下，两张卡牌的答案是(n*(n-1))/2。你不需要完整实现“n选r”就能得到这个答案。 - Mark Byers

请参阅https://dev59.com/m0rSa4cB1Zd3GeqPTyXF以获取实现考虑事项。 - mob

哦，好的，非常感谢，你是正确的，我有整数溢出问题。 - Aly

@MarkByers。一个好的(n, r)实现永远不会计算完整的阶乘！ - Mad Physicist

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!

因此，这给了我们一个简单的起点，使用上面的公式，我们可以找到任何K>0的(N choose K)，只需进行K次乘法和K次除法。

---

简单的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"

根据谷歌（Google）的说法，133个数中选择71个数的组合数 = 5.55687037 × 10³⁸。

---

参考资料

• Wikipedia/二项式系数
• Wikipedia/帕斯卡三角形
• Wikipedia/组合

- polygenelubricants

---

我注意到使用这种方法（而非递归计算）可以大大提高性能。 - pkmiec

你的打印帕斯卡三角形的解决方案对于大数不起作用。以30为例。 - Markymark

关于你的二项式函数的一点实现注意事项：可以将迭代范围改为最小值(N-K, K)，而不是迭代到K。 - Håvard Geithus

很好的解释！我们如何证明 (n-k)/(k+1) * nCk 永远不会得到浮点数？ - rahs

非常棒的解释。非常感谢。 - rick Sarkar

Answer 2

Apache Commons的“Math”库可以实现这一功能，使用方法如下： org.apache.commons.math4.util.CombinatoricsUtils

- theomega

---

之前的链接都无法使用了，哈哈！Apache的工作人员应该负责将旧链接重定向到更新的信息页面。 - Fran Marzoa

http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math4/util/CombinatoricsUtils.html - arve0

这个链接直接计算的是斯特林数S2，但并不是组合数。正确的方法是使用binomialCoefficient()，请参考https://commons.apache.org/proper/commons-math/javadocs/api-3.3/org/apache/commons/math3/util/CombinatoricsUtils.html#binomialCoefficient(int,%20int) - Cohensius

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

优化这个函数的运行时间留给读者 练习 :)

- dimo414

---

我不想挑毛病，但我真的很好奇为什么我的回答被踩了。当然，polygenelubricants的回答更详细，但我已经多次使用这个函数而没有问题，难道有什么错误吗？ - dimo414

我没有给你的帖子投反对票，但是你的算法会调用2C(n,k)-1次。也就是说，在计算'choose(10,5)'时，它将会进行503次递归调用（2C(10,5)-1=2*252-1=504-1）。因此，它无法计算C(40,20)，这大约是1380亿次。 - ErikR

同意，基本的斐波那契实现或任何从动态规划中受益的算法也是如此。您认为我的答案（特别是建议记忆化方法）没有充分涵盖吗？ - dimo414

如果你在编写代码时包含了记忆化技术，也许就不会被踩了。现在的情况是，它并不是很实用。但有些人认为你的回答还是有贡献的，因为你得到了一些赞。 - ErikR

是的，也许吧。就我个人而言，动态规划与实际问题无关，不同的应用需求将需要不同的缓存方案，但我会承认有人可能会感到不满，因为这个答案不能直接使用。无论如何，我会尽量不因此失眠 :) - dimo414

点赞。使用哈希表可以轻松改进时间复杂度。 - Tao Zhang

Answer 4

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

无需导入外部库-根据组合的定义，使用 n 张卡牌会得到 n*(n-1)/2 种组合。

奖励问题:这个公式也可以计算前 n-1 个整数的和 - 你看出它们为什么相同了吗？ :)

- BlueRaja - Danny Pflughoeft

---

（一年后的奖励问题答案：第一张牌有n-1种与另一张牌配对的方法，第二张牌有n-2种与剩余牌配对的方法，以此类推。） - BlueRaja - Danny Pflughoeft

Answer 5

binomialCoefficient，在Commons Math中，返回二项式系数的精确表示，即从n个元素集合中选择k个元素的组合数。

返回二项式系数的精确表示，即从n个元素集合中选择k个元素的组合数。

- Valentin Rocher

Answer 6

N!/((R!)(N-R)!)

在这个公式中，有很多可以约分的部分，所以通常阶乘不是问题。假设R > (N-R)，那么将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 := max(R, N-R)+1
for (m := r+1,d := 2; m <= N; m++, d++ ) {
    r *= m
    r /= d
}

- malach

Answer 7

以下程序将使用递归定义和备忘录计算n选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;
}

- Matthieu N.

---

这是C++，不是Java。 - phw

@phw。转换为Java所需的工作量很少。 - Mad Physicist

我认为Java没有内联函数。你可以移除inline关键字，对吧？ - Yolomep

Answer 8

这个的数学公式为：

N!/((R!)(N-R)!)

从那里开始，应该不难弄清楚 :)

- Aistina

---

是的，确实应该这样做。比如说，如果你受到“int”数据类型的限制，你就不想计算巨大的阶乘。 - Josh Lee

@jleedev：就算一开始对那个进行因式分解也不会太难 :P - Esko

你可以进行一些因式分解来使其更加简洁，但是这个定义仍然适用于比你想要使用的数字要大得多的情况。为了获得最佳结果，选择算法不应计算比结果更大的数字 - 因为它们会变得非常快。 - dimo414

@dimo414。如果您按照原样实现，它每次都会溢出。如果您从R!和（N-R）！中较大的数中删除所有因子，然后利用结果始终为整数的事实，您就不需要担心中间结果的溢出问题。 - Mad Physicist

Answer 9

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

- Kruti Rao Erraguntala

Answer 10

guava 包含 IntMath#binomial(int, int)、LongMath#binomial(int, int) 和 BigIntegerMath#binomial(int, int)。

- Olivier Cailloux