5/3團練記錄

參考網站：http://www.csie.ntnu.edu.tw/~u91029/Permutation.html

做了一題練習
因為在審題上出了問題
An upper case letter goes before the corresponding lower case letter.
這一句話的意思是
當我們在排序時
大寫是在小寫前面的
所以
比如說input是
AaBbCc
在沒有處理的前提下
第一個output可能會變成
ABCabc //也就是字典順序
這一點要注意

/*JW's AC Code in ACM 195*/

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define MAX 1024

char Input[MAX];    //輸入
char ans[MAX];      //存排列的結果
char used[MAX];     //用過的

int cmp1(const void *a,const void *b)
{
    return (*(char*)a-*(char*)b);
}

//Quick Sort用
int cmp2(const void *a,const void *b)
{
    return (tolower(*(char*)a)-tolower(*(char*)b));
}

//排列
void p(int k,int len)
{
    if(k==len)
    {
        int i;
        for(i=0;i<len;i++)printf("%c",ans[i]);
        printf("\n");
        return;
    }
    char LastLetter='\0';
    int i;
    for(i=0;i<len;i++)
    {
        if(used[i]==0 && LastLetter!=Input[i])
        {
            LastLetter=Input[i];
            used[i]=1;
            ans[k]=Input[i];
            p(k+1,len);
            used[i]=0;
        }
    }
}

int main()
{
    int N;
    scanf("%d",&N);
    int i;
    for(i=0;i<N;i++)
    {
        scanf("%s",Input);
        int len=strlen(Input);
        int j;
        for(j=0;j<len;j++)used[j]=0;
        qsort(Input,len,sizeof(char),cmp1);
        qsort(Input,len,sizeof(char),cmp2);
        p(0,len);
    }
    return 0;
}

/*ApplerMan's AC Code in ACM 195*/
#include<stdio.h>
#include<string.h>
#define MAX 1000

int charNum[52],length;
char solution[MAX];//解答

void permutation(int k,int n){
        int i;
        if(k==n){
                for(i=0;i<n;i++){
                        printf("%c",solution[i]);        
                }
                printf("\n");
                return ;
        }
        for(i=0;i<52;i++){
                if(charNum[i]>0){        
                        charNum[i]--;
                        if(i%2==0){
                                solution[k]=(i/2)+'A';//取出來
                        }
                        else{
                                solution[k]=(i/2)+'a';//取出來
                        }
                        permutation(k+1,n);
                        charNum[i]++;
                }
        }
}

void input(void){
        int i;
        char str[MAX];
        gets(str);
        length=strlen(str);
        for(i=0;i<length;i++){
                if('A'<=str[i]&&str[i]<='Z'){
                        charNum[(str[i]-'A')*2]++;//編入
                }
                else if('a'<=str[i]&&str[i]<='z'){
                        charNum[(str[i]-'a')*2+1]++;//編入
                }
        }
}

void init(void){
        int i;
        for(i=0;i<52;i++)
                charNum[i]=0;        
}

int main(void){
        int N;
        scanf("%d\n",&N);
        while(N--){
                init();//負責初始化
                input();//輸入部分
                permutation(0,length);//遞迴
        }
        return 0;
}

//charNum[0]表示A的數量
//charNum[1]表示a的數量
//charNum[2]表示B的數量