<-制作不易,如果满意就点一下吧
题目描述
按照字典序输出自然数 $1$ 到 $n$ 所有不重复的排列,即 $n$ 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数 $n$。
输出格式
由 $1 \sim n$ 组成的所有不重复的数字序列,每行一个序列。
每个数字保留 $5$ 个场宽。
样例 #1
样例输入 #1
3
样例输出 #1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
提示
$1 \leq n \leq 9$。
类似题型
$\color{Red}{823. 排列}$
$\color{Red}{842. 排列数字}$
$\color{Red}{51. 数字排列}$
$\color{Red}{3429. 全排列}$
方法一:
这是一道好题,用STL的好题
在#include <algorithm>里有一个函数,全排列函数:
next_permutation!
仅需15行代码即可AC!
$code$:
#include<bits/stdc++.h>
#define for(a,b,c) for(register int a = b; a <= c; a ++)
using namespace std;
int x[11];
int main(){
int n;
scanf("%d",&n);
for(i,1,n) x[i] = i, printf(" %d", i);
while(next_permutation(x + 1, x + 1 + n)){
printf("\n");
for(i,1,n) printf(" %d", x[i]);
}
return 0;
}
$\color{Red}{STL yyds}$
方法二:
其实可以直接用main()来递归!
$code$:
#include<bits/stdc++.h>
using namespace std;
int n, step = 1, int i;
int a[15];
bool ans[15];
int main(){
if(step == 1){
cin >> n;
}
if(step - 1 == n){
for(i = 1; i <= n; i ++){
printf("%5d", a[i]);
printf("\n");
}
}
for(i = 1; i <= n; i++){
if(ans[i] == 0){
ans[i] = 1;
a[step] = i;
step ++;
main();
step --;
ans[i] = 0;
}
}
return 0;
}
$\color{Red}{main()也可以用来递归!}$
方法三:
咱是个蒟蒻,咱不会DFS,也不会高端做法,打表费时,所以,暴力枚举出奇迹!(逃)
(不建议食用)!
其实就是枚举所有数字,很简单,n最大是9,那就用9个for循环分别枚举,从1-n,
只输出1-n的全排序,那就每个循环后面加个判断语句,看是否到第n个数了,到了的话直接输出。
$code$:
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[10], n;
for(int i = 1; i <= 9; i ++) a[i] = i;
cin >> n;
for(int i1 = 1; i1 <= n; i1 ++){//把第一个数从1-n枚举
if(n == 1){//如果n是1,即从1-1全排序
cout<<" "<<i1<<"\n"; //输出全排序结果
continue;//跳过后面几个数的枚举
}
for(int i2 = 1; i2 <= n; i2 ++){//把第二个数从1-n枚举 ,后面嵌套的for循环同理,即把第3、4、5...9个数枚举
if(i2 == i1) continue;//当i2和前面的数重复时,跳过后面的判断,继续循环。后面嵌套的循环同理,即当i3、i4、i5、......i9和前面数重复时,跳过后面的判断,继续循环
if(n == 2){//如果n是2 ,即从1-2全排序。后面同理,即从1-3、1-4......1-9全排序
cout<<" "<<i1<<" "<<i2<<"\n";//输出全排序结果,后面同理
continue;//跳过后面几个数的枚举,后面同理
}
for(int i3 = 1; i3 <= n; i3 ++){
if(i3 == i2 || i3 == i1) continue;
if(n == 3){
cout<<" "<<i1<<" "<<i2<<" "<<i3<<"\n";
continue;
}
for(int i4 = 1; i4 <= n; i4 ++){
if(i4 == i3 || i4 == i2 || i4 == i1) continue;
if(n == 4){
cout << " " << i1 << " " << i2 << " " << i3 << " " << i4 << "\n";
continue;
}
for(int i5 = 1; i5 <= n; i5++){
if(i5 == i4 || i5 == i3 || i5 == i2 || i5 == i1) continue;
if(n == 5){
cout << " " << i1 << " " << i2 << " " << i3 << " " << i4 << " " << i5 << "\n";
continue;
}
for(int i6 = 1; i6 <= n; i6++){
if(i6 == i5 || i6 == i4 || i6 == i3 || i6 == i2 || i6 == i1) continue;
if(n == 6){
cout << " " << i1 << " " << i2 << " " << i3 << " " << i4 << " " << i5 << " " << i6 << "\n";
continue;
}
for(int i7 = 1; i7 <= n; i7++){
if(i7 == i6 || i7 == i5 || i7 == i4 || i7 == i3 || i7 == i2 || i7 == i1) continue;
if(n == 7){
cout << " " << i1 << " " << i2 << " " << i3 << " " << i4 << " " << i5 << " " << i6 << " " << i7 << "\n";
continue;
}
for(int i8 = 1; i8 <= n; i8++){
if(i8 == i7 || i8 == i6 || i8 == i5 || i8 == i4 || i8 == i3 || i8 == i2 || i8 == i1) continue;
if(n == 8){
cout << " " << i1 << " " << i2 << " " << i3 << " " << i4 << " " << i5 << " " << i6 << " " << i7 << " " << i8 << "\n";
continue;
}
}
}
}
}
}
}
}
}
return 0;//好习惯呀!
}
本当に疲れそうです
方法四:
说实话一道简单的水题做成这个样子,我也是没谁了,
经典的DFS模板真的很经典!
提醒:
printf("%5d", ans);
输出方式为 “%5d” 表示按5位的固定位宽输出整型数值。
如果不足5位,则在前面补空格;超过5位,则按实际位数输出。
#include<bits/stdc++.h>
using namespace std;
int n, ans[10];
bool a[10];
void search(int now){
if(now == n+1){
for(int i = 1; i <= n; i ++){
printf("%5d", ans[i]);
}
cout << endl;
return;
}
for(int i = 1; i <= n; i ++){
if(a[i] == false){
a[i] = true;
ans[now] = i;
search(now + 1);
a[i] = false;
}
}
}
int main(){
cin >> n;
search(1);
return 0;
}