poj 1256(Anagram + 求全排列算法)

      题目链接：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; 
}