823. 排列 (递归搜索树 · 排列)
本文最后更新于 963 天前,其中的信息可能已经有所发展或是发生改变。

823. 排列 (递归搜索树 · 排列)

原题链接
描述
给定一个整数 n,将数字 1∼n 排成一排,将会有很多种排列方法。

现在,请你按照字典序将所有的排列方法输出。

输入格式
共一行,包含一个整数 n。

输出格式
按字典序输出所有排列方案,每个方案占一行。

数据范围

1≤n≤9

输入样例:

3

输出样例:

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

分析

  • 按照字典序排列分析
  • 定义三个参数 int u用于记录当前排列的位数,int num[10]用于存放排列,bool st[10]={0}用于判断当前位置的数是否已经使用。

代码

#include <bits/stdc++.h>
using namespace std;
int n,num[10];
bool st[10]={0};
void ff(int u,int num[],bool st[]){
if(u>n){ //如果u>n说明已经排列完成,循环输出排列
for(int i=1;i<=n;i++){
cout<<num[i]<<" ";
}
cout<<endl;
}
else{
for(int i=1;i<=n;i++){ //遍历循环判断结点
if(!st[i]){ //如果该位置的数未被使用
st[i]=1; //该位置的数标记为使用
num[u]=i; //记录该位置的数
ff(u+1,num,st); //进行入下一个位置递归
st[i]=0; //将该位置回溯为未使用状态(恢复现场)
}
}
}
}
int main(){
cin>>n;
ff(1,num,st);
return 0;
}

扩展

  • 利用STL中的next_permutation函数

next_permutation按照字典序生成下一个排列组合
复杂度O(n)
排列范围[first,last)

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
int n,a[1000]; //a[]用于存放排列
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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇