题目

Description

设计算法生成n个元素{r1,r2,…,rn}的全排列。n<=10

Input

包含多组输入EOF结束，每组输入包含一个只包含小写字母的字符串，长度不超过10.

Output

输出这个字符串中所有字符的全排列，按照字典序输出。

Sample Input

abc

Sample Output

abc
acb
bac
bca
cba
cab

题解

样例输出有问题

cba
cab
显然不是按照字典序的

不过，不管它。

由于需要按照字典序输出，因此不管输入的是abc还是cba答案都应该是一样的

因此，为了后面方便，可以使用sort先将字符串排成字典序

然后使用递推来找到所有的组合

可以将传一个已经参数char out[]表示已经这组输出前面部分的字符串
每次将一个还没有输出过的数放进去即可

关于还没有输出过的数的判断
按照我的思路应该是对于aa中的两个a应该是两个不同的字符
也即输入

aa

输出的应该是

aa
aa

不过貌似数据没有卡这一方面。

如果按照我的思路，那么可以用一个bool数组来记录该位置的数是否已经输出。

递归到最后一层，在字符串后面加上\0，然后输出字符串即可。

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/
 
かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
//const int INF = (2<<30)-1;
 
const int maxn = 15;
char s[maxn];
bool flag[maxn];
char out[maxn];
 
void DFS(char *s,int pos) {
    int len = strlen(s);
    if(pos == len) {
        out[pos] = '\0';
        printf("%s\n",out);
    }
    for(int i = 0;i < len;i++) {
        if(!flag[i]) {
            flag[i] = true;
            out[pos] = s[i];
            DFS(s,pos+1);
            flag[i] = false;
        }
    }
}
 
bool Do() {
    if(scanf("%s",s) == EOF)
        return false;
    int len = strlen(s);
    sort(s,s + len);
    memset(flag,false,sizeof(flag));
 
    DFS(s,0);
    return true;
}
 
int main() {
    while(Do());
    return 0;
}