首页 > 代码库 > Generating Fast UVA 10098

Generating Fast UVA 10098

说说:

这道题的其实就是给你一个字符串,然后输出该字符串所含字符能构成的全部的串,并按字典升序输出。解法的话,无非就是递归实现。先将原字符串排序,然后逐一确定每个位置上的字符。为了防止有重复的字符串出现,每个位置上的字符不能与之前相同。具体的解释请参见刘汝佳的《算法竞赛入门经典》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]='\0';
   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('\n');
  }

  return 0;
}

void print_permutation(int cur){
  int i,j,c1,c2;

  if(cur==N){
    printf("%s\n",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;
}


Generating Fast UVA 10098