枚举、全排列.md

枚举 \ 全排列

next_permutation，algorithm自带的枚举函数，可以将传入的数组里面的数进行枚举，时间复杂度 $O(n!)$ 。

注意：有一个坑点，那就是结果是从初始化时的字典序位置开始，直到最大字典序位置！比如初始为[3,1, 2]，则得到的是[3,1,2]，[3,2,1]就结束了。

int nums[] = {1, 2, 3, 4}; // 从初始化的位置开始按照字典序增加排列
do
{
    cout << nums[0] << ' ' << nums[1] << ' ' << nums[2] << ' ' << nums[3] << endl;
}
while(next_permutation(nums, nums + 4));

朴素写法

// 其实就是一个全排列
long long n;
int pre[100]; // 记录每一个枚举的顺序
int flag[100];

int main() {
	for (int i = 0; i < n; i ++) {
	        bfs(0);
	}
}

void bfs(int cnt) {
    if (cnt == n) {
        // 具体逻辑
    }
    for (int i = 0; i < n; i ++) // 全排列没有选与不选 只是选的顺序不一样
        if (!flag[i]) {
            flag[i] = true;
            pre[cnt] = i;
            bfs(cnt + 1);
            flag[i] = false;            
        }
}

全排列的变体： 在 n 个数中选 k 个进行排列。

递归实现

vector<int> temp;
void dfs(int cur, int n) {
    if (cur == n + 1) {
        // 记录答案 输出temp
        // ...
        return;
    }
    // 考虑选择当前位置
    temp.push_back(cur);
    dfs(cur + 1, n, k);
    temp.pop_back();
    // 考虑不选择当前位置
    dfs(cur + 1, n, k);
}