常见的枚举方式

  |  

摘要: 本文梳理一下常见的枚举方式,以及对应的代码模板

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


枚举与分类讨论找规律按位单独处理分别计算各元素贡献逆向思维惰性更新 等一样,也是一种思想技巧,而很难归为某个具体算法。实践中需要再具体问题中灵活应用。

虽然这种思想性的东西在实际问题中的应用是很灵活的,但还是有一些套路性的东西的,本文就总结一下常见的枚举方式,并给出对应的代码模板。主要内容如下:

  • 多项式型枚举:欧式空间的坐标
  • 指数型枚举:子集
    • 无重
      • DFS
      • 位运算
    • 有重
      • DFS
  • 排列型枚举:排列
    • 无重
      • DFS(字典序)
    • 有重
      • DFS(字典序)
  • 组合型枚举:组合
    • 无重
      • DFS
      • 递推
      • 二进制字典序

$1 多项式型枚举:欧式空间的坐标

  • 枚举方式:for 循环
  • 状态空间规模:$n^{k}$
1
2
3
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
...

$2 指数型枚举:子集

  • 枚举方式:递归,位运算
  • 状态空间规模:$k^{n}$

无重复集合:78. 子集

实现1: DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int> > result;
vector<int> list;
dfs(nums, 0, list, result);
return result;
}

private:
void dfs(vector<int> &nums, int pos, vector<int> &list, vector<vector<int> > &result)
{
int n = nums.size();
if(pos == n)
{
result.push_back(list);
return;
}
list.push_back(nums[pos]);
dfs(nums, pos + 1, list, result);
list.pop_back();
dfs(nums, pos + 1, list, result);
}
};

实现2: 位运算

从 0 开始增加,到 1 << n 为止。

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
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int> > results;
int n = nums.size();

vector<int> result_item;
unsigned int map = 0;
unsigned int end = 1 << n; // 停止边界

while(map < end)
{
for(int i = 0; i < n; ++i)
{
if((1 << i) & map)
result_item.push_back(nums[i]);
}
results.push_back(result_item);
// 只清空元素,不释放内存
// vector<int>().swap(MyObject)可以清空元素,释放内存。
result_item.clear();
++map;
}
return results;
}
};

有重复集合:90. 子集 II

实现: DFS

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
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int> > result;
if(nums.empty()) return result;
sort(nums.begin(), nums.end());
vector<int> list;
vector<int> visited(nums.size(), false);
dfs(nums, 0, list, result, visited);
return result;
}

private:
void dfs(vector<int> &nums, int pos, vector<int> &list,
vector<vector<int> > &result, vector<int> &visited)
{
int n = nums.size();
if(pos == n)
{
result.push_back(list);
return;
}
if(pos > 0 && nums[pos] == nums[pos - 1] && !visited[pos - 1])
{
visited[pos] = false;
dfs(nums, pos + 1, list, result, visited);
}
else
{
list.push_back(nums[pos]);
visited[pos] = true;
dfs(nums, pos + 1, list, result, visited);
list.pop_back();
visited[pos] = false;
dfs(nums, pos + 1, list, result, visited);
}
}
};

$3 排列型枚举:排列

  • 枚举方式:递归,迭代器(next_permutation)
  • 状态空间规模:$n!$

无重复排列:46. 全排列

实现: DFS(字典序输出)

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
28
29
30
31
32
33
34
35
class Solution {
public:
vector<vector<int> > permute(vector<int>& nums) {
vector<vector<int> > result;
if(nums.empty()) return result;
vector<int> cur_path;
int n = nums.size();
vector<bool> visited(n, false);
dfs(nums, 0, cur_path, result, visited);
return result;
}

private:
void dfs(vector<int> &nums, int pos, vector<int> &cur_path,
vector<vector<int> > &result, vector<bool> &visited)
{
// pos 是当前考虑的路径的位置
int n = nums.size();
if(pos == n)
{
result.push_back(cur_path);
return;
}
for(int i = 0; i < n; ++i)
{
if(visited[i]) continue;
cur_path.push_back(nums[i]);
visited[i] = true;
dfs(nums, pos + 1, cur_path, result, visited);
cur_path.pop_back();
visited[i] = false;
}
return;
}
};

有重复排列:47. 全排列 II

实现: DFS(字典序输出)

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
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int> > result;
if(nums.empty()) return result;
vector<int> cur_path;
int n = nums.size();
vector<bool> visited(n, false);
sort(nums.begin(), nums.end());
dfs(nums, 0, cur_path, result, visited);
return result;
}

private:
void dfs(vector<int> &nums, int pos, vector<int> &cur_path,
vector<vector<int> > &result, vector<bool> &visited)
{
// pos 是当前考虑的路径的位置
int n = nums.size();
if(pos == n)
{
result.push_back(cur_path);
return;
}
for(int i = 0; i < n; ++i)
{
if(visited[i]) continue;
if(i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;
cur_path.push_back(nums[i]);
visited[i] = true;
dfs(nums, pos + 1, cur_path, result, visited);
cur_path.pop_back();
visited[i] = false;
}
return;
}
};

$4 组合型枚举:组合

  • 枚举方式:递归(+剪枝)
  • 状态空间规模:$\dbinom{n}{m}$

无重复组合:77. 组合

实现1: DFS(字典序输出)

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
28
29
30
31
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
if(n < 1) return vector<vector<int> >();
if(k > n) return vector<vector<int> >();
// n >= 1, k <= n
int pos = 1;
vector<vector<int> > results;
vector<int> result_item;
dfs(results, result_item, pos, n, k);
return results;
}

private:
void dfs(vector<vector<int> >& results, vector<int>& result_item, int pos, int n, int k)
{
int cur_len = result_item.size();
if(cur_len == k)
{
results.push_back(result_item);
return;
}
if(n - pos + 1 + cur_len < k) return; // 剪枝
if(pos > n) return;

result_item.push_back(pos);
dfs(results, result_item, pos + 1, n, k);
result_item.pop_back();
dfs(results, result_item, pos + 1, n, k);
}
};

实现2: DP,利用组合的递推式

1
C(n, k) = C(n - 1, k - 1) + C(n - 1, k - 1)
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
28
29
30
31
32
class Solution_2 {
public:
vector<vector<int>> combine(int n, int k) {
if(n < 1) return vector<vector<int> >();
if(k > n) return vector<vector<int> >();
// k == 1 和 n == k 是递归的关键
if(k == 1)
{
vector<vector<int> > results;
for(int i = 1; i <= n; ++i)
results.push_back(vector<int>({i}));
return results;
}
if (n == k)
{
vector<int> row;
for (int i = 1; i <= n; ++i)
row.push_back(i); // select all
vector<vector<int> > results;
results.push_back(row);
return results;
}

vector<vector<int> > results = combine(n - 1, k - 1);
for(vector<int>& result_item: results)
result_item.push_back(n);

vector<vector<int> > results2 = combine(n - 1, k);
results.insert(results.end(), results2.begin(), results2.end());
return results;
}
};

实现3: 二进制字典序

大致过程如下面的例子:

1
2
3
4
5
6
7
e.g. 1, 2, 3, 4  C(4, 2)
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0

二进制字典序是性能最优的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution_3 {
public:
vector<vector<int>> combine(int n, int k) {
vector<int> nums(k, 0);
for(int i = 1; i <= k; ++i)
nums[i - 1] = i;
nums.push_back(n + 1); // 哨兵

vector<vector<int> > results;
int j = 0;
while(j < k)
{
results.push_back(vector<int>(nums.begin(), nums.begin() + k));
j = 0;
while(j < k && nums[j + 1] == nums[j] + 1)
{
nums[j] = j + 1; // 关键一行
++j;
}
++nums[j];
}
return results;
}
};

Share