2010年9月17日 星期五

ACM 195 - Anagram

#include <stdio.h>
#include <string.h>
#define MAXLEN 35

char str[MAXLEN];
char compStr[] = {'A','a','B','b','C','c','D','d','E','e','F','f','G','g','H','h','I','i','J','j'
,'K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R','r','S','s','T','t'
,'U','u','V','v','W','w','X','x','Y','y','Z','z'};

int comp(char ch1, char ch2)
{
int i, ch1i, ch2i;
for (i = 0; i < strlen(compStr); i ++)
if (ch1 == compStr[i]) ch1i = i;
for (i = 0; i < strlen(compStr); i ++)
if (ch2 == compStr[i]) ch2i = i;
if (ch1i < ch2i) return 1;
else return 0;
}

void swap(int i, int j)
{
char tmp;
tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}

int next_permutation()
{
int i, j, k;
int length;
length = strlen(str);
for(i = length - 1;i > 0 ; --i)
if(comp(str[i-1], str[i])) break;
j = i;
if(j == 0) return 0;
for(i = length - 1;i > 0; --i)
if(comp(str[j-1], str[i])) break;
k = i;
swap(j-1, k);
for(i = j, j = length - 1;i < j; ++i, --j)
swap(i, j);
return 1;
}

void sort()
{
int i, j;
char ch;
for (i = strlen(str) - 1; i >= 0; i--)
for (j = 0; j < strlen(str); j++)
if (comp(str[strlen(str) - j - 1], str[i]) )
ch = str[strlen(str) - j - 1], str[strlen(str) - j - 1] = str[i], str[i] = ch;
}

int main()
{
int n, i;
scanf("%d", &n);
getchar();
for (i = 0; i < n; i ++)
{
gets(str);
sort();
printf("%s\n", str);
while (next_permutation())
printf("%s\n", str);

}
return 0;
}

回目錄
回首頁

沒有留言 :

張貼留言

Related Posts Plugin for WordPress, Blogger...