Generating Fast UVA 10098
来源：程序员人生 发布时间：2014-10-08 18:19:29 阅读次数：1906次
说说：
这道题的其实就是给你一个字符串，然后输出该字符串所含字符能构成的全部的串，并按字典升序输出。解法的话，无非就是递归实现。先将原字符串排序，然后逐一确定每个位置上的字符。为了防止有重复的字符串出现，每个位置上的字符不能与之前相同。具体的解释请参见刘汝佳的《算法竞赛入门经典》P118，生成可重集的排列。
源代码：
#include <stdio.h>
#include <string.h>
#define MAX 10+5
char s[MAX];
char p[MAX];
int N;
void print_permutation(int);
int main(){
int n,j,i;
char c;
// freopen("data","r",stdin);
scanf("%d",&n);
while(n--){
scanf("%s",s);
N=strlen(s);
p[N]=' ';
for(i=1;i<N;i++)//先将原字符串排序
for(j=i;j>0;j--)
if(s[j]<s[j-1]){
c=s[j];
s[j]=s[j-1];
s[j-1]=c;
}
print_permutation(0);
putchar('
');
}
return 0;
}
void print_permutation(int cur){
int i,j,c1,c2;
if(cur==N){
printf("%s
",p);
return ;
}
for(i=0;i<N;i++)
if(!i||s[i]!=s[i-1]){//保证所得字符串不重复
c1=c2=0;
for(j=0;j<cur;j++) //统计当前字符在已生成的p中出现的次数
if(s[i]==p[j]) c1++;
for(j=0;j<N;j++)//统计当前字符在s中出现的总次数
if(s[i]==s[j]) c2++;
if(c1<c2){
p[cur]=s[i];
print_permutation(cur+1);
}
}
return;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
