数组合数学

字典序法枚举组合

字数统计: 1.4k字   |   阅读时长: 6分
,

摘要: 按照字典序来枚举组合 $\binom{n}{r}$

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 字典序法枚举排列 中，我们用字典序方法完成了排列的枚举。在 C++ 中，std::next_permutation 和 std::prev_permutation 是字典序法实现的。

不过 C++ 中没有提供 combination 相关的函数，本文我们就来看一下如何用字典序法实现组合的枚举。

枚举组合的问题

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

提示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1 <= n <= 20
1 <= k <= n

>示例 1：
>输入：n = 4, k = 2
>输出：
>[
>  [2,4],
>  [3,4],
>  [2,3],
>  [1,2],
>  [1,3],
>  [1,4],
>]
>
>示例 2：
>输入：n = 1, k = 1
>输出：[[1]]

字典序法

1 ~ n 中取 r 个数字，取出的数字集合记为 comb，由于组合不关心顺序，因此不妨设 comb[0] < comb[1] < ... < comb[r-1]。

在此基础上，$\binom{n}{r}$ 种组合可以按字典序进行排序，我们要做的是找到一种推导方式，可以把这些组合按字典序从小到大一个一个推出来。

有两种理解方式，一种是按 r 位 n 进制数的理解方式来推导，另一种是按表示 r-子集的 01 数组的排列的理解方式来推导，两种推导方式的结果相同，下面分别来看。

用 r 位 n 进制数理解

从 ${1, 2, \cdots, n}$ 中取 r-组合，记为 comb，表示为 comb[0], comb[1], ..., comb[r-1]，满足以下两个条件：

  • comb[0] < comb[1] < ... < comb[r - 1]
  • i + 1 <= comb[i] <= n - r + 1 + i

第一个组合为 {1, 2, ..., r}，后续组合的生成规则如下：

1
2
3
4
扫描 comb，找到满足 comb[i] < n - r + i + 1 的最大的 i：
    令 comb[i] 为 comb[i] = comb[i] + 1
    对后续的 comb[i + 1], comb[i + 1], ..., comb[r - 1] 进行修改，即：
        comb[j] = comb[j - 1] + 1, i + 1 <= j < r

上面的生成顺序可以大致理解为 r 位 n 进制数，r 个位的数字均不同，从小到大的顺序，只是数字集合从 $0,1,\cdots,n-1$ 平移到 $1,2,\cdots,n$。

比如对于 n = 5, r = 3 来说，10 种可能的组合按照字典序从小到大如下：

1
2
3
4
5
6
7
8
9
10
1, 2, 3
1, 2, 4
1, 2, 5
1, 3, 4
1, 3, 5
1, 4, 5
2, 3, 4
2, 3, 5
2, 4, 5
3, 4, 5

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combine(self, n: int, r: int) -> List[List[int]]:
        # 利用字典序法生成 1 ~ n 选 r 的组合 
        comb = [i + 1 for i in range(r)]
        result = []
        while True:
            result.append(comb.copy())

            i = r - 1
            while i >= 0 and comb[i] == n - r + i + 1:
                i = i - 1

            if i == -1:
                break

            # 下一个组合
            comb[i] = comb[i] + 1
            for j in range(i + 1, r):
                comb[j] = comb[j - 1] + 1

        return result

用表示 r-子集的 01 数组的排列理解

从 1 ~ n 中选出 r 个数，对每个数来说都有选或不选两种可能，如果选了，记一个 0，如果没选，记一个 1，这样我们得到了一个长为 $n$ 的由 0 和 1 组成的数组，我们称其为 r-子集数组，记为 subset_r，其中由 $r$ 个 0，$n - r$ 个 1。

例如 $n = 5, r = 3$，从 1 ~ 5 中选出的 3 个数为 1, 3, 5，则对应的 r-子集数组为：[0, 1, 0, 1, 0]。

我们进一步分析二进制字典序的过程，以 n = 5, r = 3 为例，subset_r 和选出的数字的对应关系如下：

字典序排名 r-子集数组 subset_r 组合数组 comb
1 0 0 0 1 1 1, 2, 3
2 0 0 1 0 1 1, 2, 4
3 0 0 1 1 0 1, 2, 5
4 0 1 0 0 1 1, 3, 4
5 0 1 0 1 0 1, 3, 5
6 0 1 1 0 0 1, 4, 5
7 1 0 0 0 1 2, 3, 4
8 1 0 0 1 0 2, 3, 5
9 1 0 1 0 0 2, 4, 5
10 1 1 0 0 0 3, 4, 5

可以看到，r-子集的排列与 1 ~ n 选 r 个数的选法一一对应。并且 subset_r 中 0 的位置表示选出的数字时，subset_r 的二进制字典序与组合 comb 的字典序也是对应的。

因此我们可以枚举 r-子集数组的所有排列，就相当于枚举了 1 ~ n 选 r 个的所有组合。按字典序枚举 r-子集，则组合数组 comb 也是按其字典序枚举出来的。

用字典序法枚举 r-子集数组的所有排列，参考文章 字典序法枚举排列。

代码 (C++)

先枚举排列 subset_r，然后将 subset_r 转换为选出的组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> combine(int n, int r) {
        vector<int> subset_r(n, 1);
        for(int i = 0; i < r; ++i)
        {
            // 字典序最小的选法
            // 前 r 个为 0，表示选出 1,2,...,r
            subset_r[i] = 0;
        }
        vector<vector<int> > result;
        do{
            result.push_back(vector<int>(r));
            int m = result.size();
            int j = 0;
            for(int i = 0; i < n; ++i)
            {
                if(subset_r[i] == 0)
                    result[m - 1][j++] = i + 1;
                if(j == r)
                    break;
            }
        }
        while(next_permutation(subset_r.begin(), subset_r.end()));
        return result;
    }
};
Share