枚举¶
1 子集枚举¶
子集枚举是枚举一个数组的所有子集的操作。
基本思想¶
对于一个元素总数为 \(n\) 的数组，用位数不超过 \(n\) 的二进制数 \(S\) 表示。若从低到高第 \(i\) 位值为 \(1\) ，则表示数组中第 \(i\) 个元素属于该子集，若位值为 \(0\) ，则表示不属于该子集。如 \((10011)_2\) 表示数组中下标为 \(0\) , \(1\) , \(4\) 的元素属于该子集。
相关操作需要使用位运算。 1 << i 表示将 \(1\) 左移 \(i\) 位，即为 \(2^i\) 。 S & (1 << i) 的与运算表示判断第 \(i\) 位是否为 \(1\) ，即判断 \(S\) 是否包含下标为 \(i\) 的元素。
复杂度分析¶
- 时间复杂度： \(O(2^n)\)
- 空间复杂度： \(O(1)\)
注意事项¶
二进制数最低位为 \(2^0\) ，即 1 << 0 ，因此数组 \(a\) 的元素必须从下标 \(0\) 开始。
示例¶
int U = 1 << n; // U = 2^n, 表示全集
for (int S = 0; S < U; S++) { // 枚举子集 S
for (int i = 0; i < n; i++) { // 枚举子集中的元素
if (S & (1 << i)) cout << a[i] << ' ';
}
cout << endl;
}
如果要限制子集元素个数，可配合 __builtin_popcount() 函数进行判断。该函数作用是判断一个数二进制形式下有多少位值为 \(1\) 。
限制子集中元素个数为 \(2\) ：
int U = 1 << n;
for (int S = 0; S < U; S++) {
for (int i = 0; i < n; i++) {
if (__builtin_popcount(S) != 2) continue; // 限制子集元素个数
if (S & (1 << i)) cout << a[i] << ' ';
}
if (__builtin_popcount(S) == 2) cout << endl;
}
2 排列枚举¶
排列枚举是枚举一个数组的全排列的操作。
基本操作¶
使用 C++ STL 中的 next_permutation 函数，其能够生成序列的下一个字典序排列，适合全排列枚举。
- 头文件：
#include <algorithm> - 用法：
next_permutation(begin, end);。其中 \(begin\) 和 \(end\) 分别为数组首元素地址和末元素后一位的地址。 - 返回值：如果存在下一个排列，返回
true，否则返回false并将序列变为最小排列。
复杂度分析¶
- 时间复杂度： \(O(n!)\)
- 空间复杂度： \(O(1)\)
注意事项¶
全排列时要事先将所有元素升序排序，并将其作为第一种排列。
示例¶
int a[3] = {1, 2, 3};
do {
for (int i = 0; i < 3; i++) cout << a[i] << " ";
cout << endl;
} while (next_permutation(a, a + 3)); // 生成下一个排列
示例输出：