AOJ 805.算法期末考试A(全排列问题)

194

题目


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;
}

发布评论
  • 点击查看/关闭被识别为广告的评论