目录

主函数

用来排序的函数

 详细过程

代码

从键盘输入一个没有重复元素的字符串，输出这个字符串所有字符的全排列

输入格式:

一个字符串，输入保证字符串中没有重复的字符，字符串的长度不超过10，字符串中不含空格。

输出格式:

按字典序输出该字符串所有字符的全排列。每个字符之间没有空格。每种排列之间换行。

输入样例1:

ABC

输出样例1:

ABC
ACB
BAC
BCA
CAB
CBA

输入样例2:

CAB

输出样例2:

ABC
ACB
BAC
BCA
CAB
CBA

输入样例3:

ATOM

输出样例3:

AMOT
AMTO
AOMT
AOTM
ATMO
ATOM
MAOT
MATO
MOAT
MOTA
MTAO
MTOA
OAMT
OATM
OMAT
OMTA
OTAM
OTMA
TAMO
TAOM
TMAO
TMOA
TOAM
TOMA

思路：

        首先分析题目，我们可以知道这个跟正常的全排列一样，唯一的区别只是关于需要在最后排个序，但是我们可以在一开始就将所有的字符排一个序，然后我们的结果就是有序的。

        那么现在我们唯一的问题就是如何进行全排列，这里我选择的是dfs，接下来我会用debug讲解详细的过程。 

        在开始用debug讲解之前先让我们了解一下基本的代码。

主函数

int main(){
    //用来排序的数组
    char b[20];
    cin>>b;

    //后面用来判断当前字母排过序没有
    int dp[20]={0};

    int n=0;
    //来数一共有几个字母需要排序
    while(b[n]!='\0')
    {
        n++;
    }

    //将需要排序的数组来排个序，确保后面输出的结果顺序是从小到大，一般的全排序不需要这一步
    sort(b,b+n);
    //（排序的数组，判断是否排过，数组大小，当前位置）
    pai(b    ,       dp    ,      n,        0);
    return 0;
}

用来排序的函数

//注意，这个数组我没有放到函数里面，而是当作了一个全局变量，用来装我们排序的数组
char arr[20];

void pai(char b[],int dp[],int n,int wei)
{
    //判断是否已经将全部字母排完序
    if(wei==n)
    {
        //输出结果
        for(int i=0;i<n;i++)
        {
            cout<<arr[i];
        }
        cout<<endl;
        return ;
    }
    //从新遍历一遍数组
    for(int i=0;i<n;i++)
    {
        //判断是否已经排序了
        if(dp[i]==0)//要是没有排序
        {
            //就将当前字母加入arr，等等需要输出
            arr[wei]=b[i];
            //标记为已经排过序
            dp[i]=1;
            //去寻找下一个字母
            pai(b,dp,n,wei+1);
            //重新标记为没有排序，然后退出该循环
            dp[i]=0;
        }
    }
    return ;
}

 详细过程

        当前步骤是那个倒着的小黄三角形，然后右边有一条竖线那个

        现在我们已经输入完了数据，这里我用的是ABC

        

       然后我们进入while循环，找到当前一个有几个字母需要我们排序

 

         这里我相信大家一定知道，就先多跳过一点。

        然后就是这个sort函数，这个是我们用来排序的，默认是从小到大，这个其实你也可以用手写的冒泡或者快排之类的代替，反正都一样。

        一般的全排列不需要，这里只是题目需要，最后输出的结果需要有一个顺序所以才加上了。

        然后就进入到排序的函数

 

        首先第一个执行的语句是if(wei==n),意识是判断当前我们是否已经将字母排完序了，如果排完了就可以输出结果，否者的话就跳过。

        这里由于是在第一次排A，所以我们的wei此时是0，n是一个需要排序的字母有几个，所以此时是3，得出结论：当前不满足条件。

         现在开始遍历一遍b数组，然后挨个判断当前字母是否排过序的。

        首先判断的是A，还没有排过序，所以就满足条件会进入。

        进入后，我们首先会将当前字母（A）放入arr数组，用来等等输出，然后让dp[i]=1，也就是代表dp[i]这个数(也就是A)已经排过序了，然后又调用一次函数，来寻早下一个需要排序的字母。

        此时是准备又调用一次函数，我们还是传入(b，dp，n，wei+1),wei我们需要+1,这是代表我们已经排序的字母加了1。

        现在又到了开始的位置，首先判断是否所有的字母已经排序，此时wei=1，n=3，所以还是不满住，然后就会到for那，然后有一次遍历数组。

 

 

         现在我们第一个判断的是i为0时的情况，也就是看dp[0](代表A这个位置)是否排过序，由于已经排过了，所以我们会跳过这个if，

        然后我们又回来到for这里，等等会进行i++。

        此时i为1，然后又来判断，我们可以知道这满足条件，所以我们可以进入循环。

        此时会像之前一样，将B加入arr数组，然后然后将dp[i]改为1，代表已经来过了，然后再调用一个函数。

        然后我们又会回到那个if，依旧不满足，然后到for循环那，然后A和B都会因为排过序然后跳过，到了C那时就满足条件，然后又一次调用一个函数。

        然后此时就不一样了 此时我们已经将全部字母排完序，然后可以输出众多结果中的一个。

        我们不需要不断的将arr初始化，因为我们后面会不断的用正确的答案去覆盖以前的值，所以不需要管它。

        然后我们会用return退出这个函数，回到上一个函数，也就是让arr[2]=C那个一个(我用文字描述的那个)。

        我们又重新让dp[2]=0， 相当于让已经排过序的C重新把他修改为没有排过序。然后我们又会继续进行这个for循环，但是由于已经遍历完了数组(因为i==3，n==3)，然后我们会退出for循环。

        然后会退出这一个函数，去到他的上一个函数，也就是arr[1]=B那个。

        来了后第一件事依旧是将dp[2]=0，将B也重新当作没有排过序过的，然后继续下一步。

         然后我们回到这个for，此时i=2,因为我们当时这个函数在i=1的时候就调用一个函数去了，所以现在回来后我们还可以继续这个for循环(最开始是1，然后在dp[i]=0后就结束这个if，for就会让i++)，然后就像现在这样，i=2，之后我们像前面的步骤一样，将arr[1]写入C(这个函数的wei我并没有改变，因为我是用wei+1传入的)。

        后面的就像是前面的一样了。

代码

#include <iostream>
#include<algorithm>
using namespace std;

char arr[20];
void pai(char b[],int dp[],int n,int wei)
{
    if(wei==n)
    {
        for(int i=0;i<n;i++)
        {
            cout<<arr[i];
        }
        cout<<endl;
        return ;
    }
    for(int i=0;i<n;i++)
    {
        if(dp[i]==0)
        {
            arr[wei]=b[i];
            dp[i]=1;
            pai(b,dp,n,wei+1);
            dp[i]=0;
        }
    }
    return ;
}
int main(){
    char b[20];
    cin>>b;
    int dp[20]={0};
    int n=0;
    while(b[n]!='\0')
    {
        n++;
    }
    sort(b,b+n);
    pai(b,dp,n,0);
    return 0;
}