【蓝桥杯试题】递归实现排列型枚举

💃🏼 本人简介：男
👶🏼 年龄：18
🤞 作者：那就叫我亮亮叭
📕 专栏：蓝桥杯试题

1. 题目描述

把 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

2. 代码展示

法一：dfs

#include<bits/stdc++.h>
using namespace std;const int N = 15;
int n, path[N]; //用path存储数据【保存序列】
bool vis[N];  //用vis表示是否被使用过void dfs(int x){if(x > n){  //如果超出n，则表示都填完了，那么按存储的顺序全部打印for(int i = 1; i <= n; i++){if(vis[i]) cout << path[i] << " ";}   cout << endl;return ;}//未超出的话，则需要填入x，保存在path中for(int i = 1; i <= n; i++){    //依次选择1~n中是否被使用if(!vis[i]){    //如果未被使用vis[i] = true;  //记录下来使用过，修改状态path[x] = i;    //存进path中dfs(x + 1);     //遍历下一位vis[i] = false; //回溯}}
}int main(){cin >> n;memset(path, 0, sizeof(path)); //初始化path全为0dfs(1);return 0;
}

法二：next_permutation

next_permutation/prev_permutation函数:

• next_permutation函数将按字母表顺序生成给定序列的下一个较大的排列，直到整个序列为降序为止

• prev_permutation函数与之相反，是生成给定序列的上一个较小的排列

• next_permutation(数组头地址，数组尾地址);若下一个排列存在，则返回真，如果不存在则返回假

• 若求上一个排列，则用prev_permutation

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;const int N = 15;
int n, a[N]; //利用next_permutation函数
//next_permutation(数组头地址，数组尾地址);若下一个排列存在，则返回真，如果不存在则返回假.若求上一个排列，则用prev_permutation
int main(){cin >> n;for(int i = 1; i <= n; i++){a[i] = i;}do{for(int i = 1; i <= n; i++){cout << a[i] << " ";}cout <<  endl;        }while(next_permutation(a + 1, a + n + 1));return 0;
}

最后，感谢大家支持u （^ _ ^）

如果感觉这篇文章对你有帮助的话，不妨三连支持下，十分感谢(✪ω✪)。

printf("点个赞吧*^*");

cout << "收藏一下叭o_o";

System.out.println("评论一下吧^_^");

print("关注一下叭0-0")