AcWing-94-全排列

问题

把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数n。

输出格式

按照从小到大的顺序输出所有方案，每行1个。

首先，同一行相邻两个数用一个空格隔开。

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

数据范围

1 ≤ n ≤ 9

输入样例：

3

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思路

思路一

每个位置枚举剩下可选择的数，用vis数组记录当前使用过的数字，用arr数组存放当前选择的排列数字。当枚举到最后的位置，则输出当前arr里的排列。

思路二

思路一的变形。

思路三

类似思路一，有技巧性的把使用过的数组存放在了state里，进行了状态压缩。

题解

题解一

#include<iostream>
#include<cstdio>
using namespace std;

int arr[10];
bool vis[10];
int n;

void dfs(int k) {
    if(k == n) {
        for(int i = 0; i < n; i++) {
            printf("%d ",arr[i]);
        }
        puts("");

        return;
    }

    for(int i = 0; i < n; i++) {
        if(!vis[i+1]) {
            arr[k] = i+1;
            vis[i+1] = true;
            dfs(k+1);
            vis[i+1] = false;
        }
    }
}

int main() {
    cin >> n;

    dfs(0);
    return 0;
}

题解二

/*
	回朔法---全排列问题
*/

#include<iostream>
#include<cstdio>
using namespace std;


const int maxn = 20;
int n,a[maxn];

void permute(int k) {
    int p,q;
    for (p=1; p<=n; p++) {
        for (q=1; q<k; q++) 			//若在前k-1个中存在p这个数，就直接进入下一次外部循环
            if (p==a[q]) goto next;		//否则将a[k]赋值为p，进行下一个元素k+1的放置

        a[k]=p;				//由于数组可以直接覆盖，则在完成本次递归后可以不用返回初始状态

        if (k<n) permute(k+1);
        else {
            for (q=1; q<=n; q++) printf("%d ",a[q]);
            puts("");
        }
        next:;
    }
}

int main() {
    cin>>n;
    permute(1);

    return 0;
}

题解三

/*
	状态压缩
*/
#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

int n;
vector<int> vec;

void dfs(int k,int state) {
    if(k == n) {
        for(auto x:vec) printf("%d ", x);
        puts("");
        return;
    }

    for(int i = 0; i < n; i++) {
        if(!(state >> i & 1)) {             //第i位是否使用
            vec.push_back(i + 1);
            dfs(k + 1, state | (1 << i));   //使用第i位后再往下递归
            vec.pop_back();                 //回溯
        }
    }
}

int main() {
    cin>>n;
    dfs(0,0);

    return 0;
}