首页 > 代码库 > 【字母全排列】 poj 1256

【字母全排列】 poj 1256

深搜   注意与STL模版的去重函数唯一的区别就是有去重。

#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>using namespace std;int len;char ch[15],ss[15];int visted[15];bool cmp(char a,char b){    double t1=a,t2=b;    if(a>=A&&a<=Z) t1+=31.5; //神来之笔,对于cmp的神级处理    if(t2>=A&&t2<=Z) t2+=31.5;    return t1<t2;}void dfs(int x){    if(x==len)    {        for(int i=0;i<len;++i)        printf("%c",ch[i]);        printf("\n");    }    else    {        for(int i=0;i<len;i++)  //以任意顺序开头        {            if(!visted[i])            {                ch[x]=ss[i];                visted[i]=1;                dfs(x+1);                visted[i]=0; //另一进程需要更新dfs之前的值                while(i+1<len&&ss[i+1]==ss[i])i++;  //去重            }        }    }}int main(){    //freopen("in.txt","r",stdin);    int cas;    scanf("%d",&cas);    while(cas--)    {        memset(visted,0,sizeof(visted));        scanf("%s",ss);        len=strlen(ss);        sort(ss,ss+len,cmp);        dfs(0);    }    return 0;}

 

 

网上看到的一段代码:

用的是STL的库函数next_permutation全排列

#include<cstdio>#include<iostream>#include<algorithm>#include<string>using namespace std;bool cmp(char a,char b){if(tolower(a)==tolower(b))return a<b;elsereturn tolower(a)<tolower(b);}int main(){    int t;    cin>>t;    while(t--)    {        string str;        cin>>str;        sort(str.begin(),str.end(),cmp);        do        {            cout<<str<<endl;        }        while(next_permutation(str.begin(),str.end(),cmp));    }    return 0;}

 

【字母全排列】 poj 1256