题目相关

题目描述

输出自然数 1 到 n所有不重复的排列，即 n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 n。

输出格式

由 1∼n组成的所有不重复的数字序列，每行一个序列。

每个数字保留 5个场宽。

输入输出样例

输入

3

输出

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

说明/提示

1≤n≤9

原题链接

P1706 全排列问题 - 洛谷

分析

阅读完题目之后发现，描述得还是非常简单的。先思考下在生活当中我们是如何处理这样的数学问题的。首先，为了保证不重复和遗漏，我们一般会一个数，一个数确定过去，先确定第一个数，再在这个基础上确定第二个数，再是第三个，第四个以此类推。每次都是要找不重复出现的。

再分析一下，可以发现，每次在确定第几个数字时，我们的方法都是一样的，都是从1~n的数字当中找出不重复的数字，直到我们确定好n个数字为止。

过程当中，不断发生变化的是，确定好了第几个数，已经确定了几个，以及目标是确定几个。那么，可以先构造出函数的框架出来。

void dfs(int done,int ranks[],int n){
    //done-已经选好的个数 ranks[]-选好数字的存储的地方
    //n-目标数量及范围
    //实现过程
    if(done==n){//选好的数量达到要求
        for(int i=0;i<n;i++){//输出
            cout<<ranks[i]<<" ";
        }
        cout<<endl;
    }else{
        for(int i=1;i<=n;i++){
            if(){//i没出现过
                ranks[done]=i;//存储i
                dfs(done+1,ranks,n);//用相同方法寻找下一个
            }
        }
    }
}

接着，再考虑如何进行是否重复的判断。一是可以将之前存在ranks[]中的再枚举一遍，但是这样太麻烦了。我们可以构造一个标记数组，用它来表明数字是否已经被用过了。

bool vis[10005];//vis[x]=true/fals x被使用过/没有使用过
...
for(int i=1;i<=n;i++){
            if(vis[i]==false){//i没出现过
                ranks[done]=i;//存储i
                vis[i]=true;//修改使用的状态
                dfs(done+1,ranks,n);//用相同方法寻找下一个
                vis[i]=false;//！！将状态进行回溯！！重要
            }
        }

最后注意输出的时候的特殊要求，“每个数字保留 5个场宽”。可以使用"printf("%5d")"的方式来实现。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
bool vis[15];//vis[i]=true/false i有出现过/没出现过 
void dfs(int done,int n,int ranks[]){
     //done-已经选好的个数 ranks[]-选好数字的存储的地方
    //n-目标数量及范围
    //实现过程
    if(n==done){//选好的数量达到要求
        for(int i=0;i<n;i++)
            printf("%5d",ranks[i]);
        cout<<endl;
    }else{
        for(int i=1;i<=n;i++){
            if(vis[i]==false){//i没出现过
                ranks[done]=i;//存储i
                vis[i]=true;//修改使用的状态
                dfs(done+1,n,ranks);//用相同方法寻找下一个
                //状态的回溯 
                vis[i]=false;
            }
        }
    }
}

int main(){
    int n;
    int ranks[15]={0};
    cin>>n;
    dfs(0,n,ranks); 
    return 0;
}

讲解视频

视频链接

原文：https://gitee.com/wyloving/TeachingAndLearing/blob/master/luogu/04%E9%80%92%E5%BD%92/P1706%E5%85%A8%E6%8E%92%E5%88%97%E9%97%AE%E9%A2%98.md