2010年9月17日 星期五

ACM 10098 - Generating Fast

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

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

}
return 0;
}


回目錄
回首頁

沒有留言 :

張貼留言

Related Posts Plugin for WordPress, Blogger...