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

浪漫主义狗

发布于 2022-07-11 08:46:49

4330

发布于 2022-07-11 08:46:49

文章被收录于专栏：HAUE_LYS'BlogHAUE_LYS'Blog

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

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

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

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

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

数据范围

1≤n≤9

输入样例：

输出样例：

分析：

按照字典序排列分析

定义三个参数 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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-6-15 8，如有侵权请联系 cloudcommunity@tencent.com 删除

int