0%

组合数的计算

发表于 更新于 分类于

组合数的计算虽然在一般的编程领域中不太能用到，但是在数学相关领域及ACM中还是有其用武之地的。那么，如何在程序中计算组合数呢？

累乘计算

我们知道：
$$C_{n}^{m}=\frac {A_{n}^{m}}{m!}=\frac {n!}{m!\left(n-m\right)!} , (0\leq m\leq n) \tag{1}$$
$$C_{n}^{m}=\frac {n\cdot(n-1)\ldots(n-m+1)}{m!}, (0\leq m\leq n) \tag{2}$$

通过公式(1)和公式(2)，可以简单的依据公式来进行组合数的计算。但因为公式中涉及到阶乘运算（准确说是连乘运算），故而会存在数据溢出的问题，因而不推荐。

累加计算

为了避免直接计算阶乘，可以对公式（1）两边取对数：
$$\ln(C_{n}^{m}) = \ln(n!) - \ln(m!) - \ln((n-m)!) = \sum_{i=1}^{n}\ln(i) - \sum_{i=1}^{m}\ln(i) - \sum_{i=1}^{n-m}\ln(i) \tag{3}$$
又因为：
$$\sum_{i=1}^{n}\ln(i) = \sum_{i=1}^{m}\ln(i) + \sum_{i=m+1}^{n}\ln(i) \tag{4}$$
将（4）代入等式右边可得：
$$\ln(C_{n}^{m}) = \sum_{i=m+1}^{n}\ln(i) - \sum_{i=1}^{n-m}\ln(i) \tag{5}$$

观察式（5）右侧，其累加的次数为 $[n-(m+1)+1]+[(n-m)-1+1]=2×(n-m)$次，在n的值一定的情况下，m越小，累加次数越多。
而我们知道：$C_{n}^{m}=C_{n}^{n-m}$，当 $m<n/2$ 时，直接计算 $C_n^m$ 则累加次数较多，此时，我们可以通过计算 $C_{n}^{n-m}$ 来间接得到 $C_{n}^{m}$ 的值，从而减少累加次数，提高运算效率。

最后，我们可以通过两边取e的指数幂，最终计算出组合数 $C_{n}^{m}$ 的值。

Java实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
  * 计算C(n,m)组合数的值
  */
public long combination1(int n, int m) {
    double result = 0;
    if (m > n) {
      return 0;
    }
    if (m < n / 2) {
      m = n - m;
    }
    for (int i = m + 1; i <= n; i++) {
      result += Math.log(i);
    }
    for (int i = 1; i <= n - m; i++) {
      result -= Math.log(i);
    }
    return Math.round(Math.exp(result));
}

上述方案相较于之前的累乘计算方案有明显的优化提高。值得注意的是，虽然自然常数 e 是常数，但因其为无限不循环小数，在Java代码中，实际计算时 e 取的是其近似值，所以上述代码在 n 的值较大时，会出现计算结果的偏差。n 的值较小的情况下，其准确性还是可以保障的。

精确计算

组合数公式中，还有一个恒等式：
$$C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1}, (1<m<n) \tag{6}$$

又因为：$C_{n}^{0} = C_{n}^{n} = 1$, 所以最终可以得到：
$$
C_{n}^{m} =
\begin{cases}
1 & (m = 0)\\
C_{n-1}^{m} + C_{n-1}^{m-1} & (1\leq m<n)\\
1 & (m = n)
\end{cases}
\tag{7}
$$

看到公式（7）我们很容易想到可以用递归去计算 $C_{n}^{m}$ 的值，这也不失为一种方案，然而因为在递归过程中会出现不少重复值（存在重复计算），且递归过程较为浪费栈内存，在这里就不详细介绍该方案。

我们以 $C_{5}^{3}$ 为例，建立如下矩阵：
$$
\begin{matrix}
C_0^0 & C_1^1 & C_2^2 & C_3^3 \\
C_1^0 & C_2^1 & C_3^2 & C_4^3 \\
C_2^0 & C_3^1 & C_4^1 & C_5^3
\end{matrix}
$$
在这上述矩阵中，依据公式（6），我们可以看出，每个位置上的组合数的值都等于其左边和其上边的组合数之和。也就是说，只要知道第一行和第一列各组合数的值，则可以以加法的形式计算出整个矩阵其他位置的组合值。而根据公式（7），我们知道，第一行和第一列各组合数的值均为1。

我们归纳出 $C_n^m$ 对应的矩阵：
$$
\begin{matrix}
C_0^0 & C_1^1 & C_2^2 & \cdots & C_m^m \\
C_1^0 & C_2^1 & C_3^2 & \cdots & C_{m+1}^m \\
C_2^0 & C_3^1 & C_4^2 & \cdots & C_{m+2}^m \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
C_{n-m}^0 & C_{n-m+1}^1 & C_{n-m+2}^2 & \cdots & C_n^m
\end{matrix}
$$
第1行和第1列的值均为1，可以根据第1行计算出第2行各位置的值，再可由第2行计算出第3行各位置的值，如此循环，便可计算出 $C_n^m$ 的值。

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
  * 计算C(n,m)组合数的值
  */
public long combination2(int n, int m) {
  long[] arr = new long[m + 1];
  for (int i = 0; i < arr.length; i++) {
    arr[i] = 1;
  }
  for (int i = 1; i <= n - m; i++) {
    for (int j = 1; j <= m; j++) {
      arr[j] += arr[j - 1];
    }
  }
  return arr[m];
}

上述方法，只开辟了 m+1 个长度的长整型数组，空间占有率较小，空间复杂度小。因为有两层循环，其平均时间效率不如累加的计算方案，但它是精准计算，计算出的组合数值没有偏差。综合来看，较为推荐最后这种方案来计算组合数值。

参考

组合-维基百科
组合数-百度百科
大数量级组合数的快速计算方法
基础算法学习-求组合数