题目链接:http://poj.org/problem?id=1256
题目意思:一串字符a[15],要求求出所有有这些字符构成的不重复的字符串(全排列问题)
代码借鉴于大牛处:
代码:
#include<stdio.h> #include<string.h> int n,len; int hash[15]={0}; char a[54]; char ans[15]; int dfs(int k) { int i,j; for(i=1;i<=52;i++) if(hash[i]>0) { hash[i]--; if(i % 2 == 0) ans[k]=i/2+96; else ans[k]=(i+1)/2+64; if(k == len-1) { for(j=0;j<len;j++) printf("%c",ans[j]); printf("\n"); } else dfs(k+1); hash[i]++; } return 0; } int main() { int i; scanf("%d\n",&n); while(n--) { memset(hash,0,sizeof(hash)); scanf("%s",a); len=strlen(a); for(i=0;i<len;i++) { if(a[i] >= 'A' && a[i] <= 'Z') hash[(a[i]-64)*2-1]++; else hash[(a[i]-96)*2]++; } dfs(0); } return 0; }
下面是在求解该题过程中查找的一个“递归求全排列算法”,也贴出来和大家分享下:
递归求全排列算法代码:
#include <stdio.h> inline void Swap(char& a, char& b) {// 交换a和b char temp = a; a = b; b = temp; } void Perm(char list[], int k, int m) { //生成list [k:m ]的所有排列方式 int i; if (k == m) {//输出一个排列方式 for (i = 0; i <= m; i++) putchar(list[i]); putchar('\n'); } else // list[k:m ]有多个排列方式 // 递归地产生这些排列方式 for (i=k; i <= m; i++) { Swap (list[k], list[i]); Perm (list, k+1, m); Swap (list [k], list [i]); } } int main() { char s[]="123"; Perm(s, 0, 2); return 0; }