算法竞赛进阶指南-7.递归实现排列型枚举

排列的有序性用无序的for循环实现(并且需要visited数组辅助)
组合的无序性用有序的01选择实现

题目链接

把 ${1∼n}$ 这 ${n}$ 个整数排成一行后随机打乱顺序，输出所有可能的次序 => n个数的全排列，即 ${A_n^n}$

同一行相邻两个数用一个空格隔开

对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面

Method : 递归

要记住用一个全局数组就能输出所有的排列情况。

#include <vector>
#include <iostream>

using namespace std;
const int N = 10;

int n;
vector<int> choosen;
bool visited[N] = {0};

void dfs(int depth) {
    // boundary
    if (depth == n + 1) {
        for (int i = 0; i < choosen.size(); i ++) {
            printf("%d ", choosen[i]);
        }
        cout << endl;
        return;
    }
    
    for (int i = 1; i <= n; i ++) {
        if (!visited[i]) {
            visited[i] = true;
            choosen.emplace_back(i);
            dfs(depth + 1);
            // recover
            choosen.pop_back();
            visited[i] = false;
        }
    }
}

int main() {
    cin >> n;
    dfs(1);
    return 0;
}

复杂度分析

时间复杂度 ${O(n!)}$ ，由于 $vistied[i]$ 数组，每次递归的循环执行次数会减1。并且很明显 $n!$ 与 $A_{n}^{n}$ 在数学上是相通的。
空间复杂度 ${O(N)}$ , choosen数组。

拓展求 ${A_n^m}$

Method1 : 递归

#include <vector>
#include <iostream>

using namespace std;
const int N = 10;

int n, m;

vector<int> choosen;
bool visited[N] = {0};

void dfs(int depth, int select) {
    // prune
    if (select > m || n + 1 - depth < m - select) {
        return;
    }
    
    // bounary
    if (select == m) {
        for (int i = 0; i < choosen.size(); i ++) {
            printf("%d ", choosen[i]);
        }
        cout << endl;     
        return;
    }
    if (depth == n + 1) return;
    
    for (int i = 1; i <= n; i ++) {
        if (!visited[i]) {
            visited[i] = true;
            choosen.emplace_back(i);
            dfs(depth + 1, select + 1);
            // recover
            choosen.pop_back();
            visited[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    dfs(1, 0);
    return 0;
}

复杂度分析

Method2 : ${A_n^m}$ = ${C_n^m}$ * ${A_m^m}$

利用公式定义： ${A_n^m}$ = ${C_n^m}$ * ${A_m^m}$

那么可以拆解成两个bfs，嵌套来做:

#include <vector>
#include <iostream>

using namespace std;
const int N = 10;

int n, m;

vector<int> proposal;
vector<int> choosen;
bool visited[N] = {0};

// Amm
void dfs2 (int depth) {
    if (depth == m + 1) {
        for (int i = 0; i < choosen.size(); i ++) {
            printf("%d ", choosen[i]);
        }
        cout << endl;
        return;
    }
    
    for (int i = 0; i < proposal.size(); i ++) {
        if (!visited[proposal[i]]) {
            visited[proposal[i]] = true;
            choosen.emplace_back(proposal[i]);
            dfs2(depth + 1);
            // recover
            choosen.pop_back();
            visited[proposal[i]] = false;
        }
    }
}

// Cnm
void dfs1(int depth, int select) {
    // prune
    if (select > m || n + 1 - depth < m - select) {
        return;
    }
    
    // boundary
    if (select == m) {
        dfs2(1);  
        return;
    }
    if (depth == n + 1) return;
    
    proposal.emplace_back(depth);
    dfs1(depth + 1, select + 1);
    // recover
    proposal.pop_back();
    dfs1(depth + 1, select);
}

int main() {
    cin >> n >> m;
    dfs1(1, 0);
    cout << cnt;
    return 0;
}