Anagram
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)
Total Submission(s) : 16 Accepted Submission(s) : 3
Problem Description
You are to write a program that has to generate all possible words from a given set of letters.
Example: Given the word "abc", your program should - by exploring all different combination of the three letters - output the words "abc", "acb", "bac", "bca", "cab" and "cba".
In the word taken from the input file, some letters may appear more than once. For a given word, your program should not produce the same word more than once, and the words should be output in alphabetically ascending order.
Input
The input consists of several words. The first line contains a number giving the number of words to follow. Each following line contains one word. A word consists of uppercase or lowercase letters from A to Z. Uppercase and lowercase letters are to be considered different. The length of each word is less than 13.
Output
For each word in the input, the output should contain all different words that can be generated with the letters of the given word. The words generated from the same input word should be output in alphabetically ascending order. An upper case letter goes before the corresponding lower case letter.
Sample Input
3
aAb
abc
acba
Sample Output
Aab
Aba
aAb
abA
bAa
baA
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa
Source
PKU
還是一題回溯加dfs，題目要求是把字母全排列，據說C++有個函數能夠實現，但這裡要求按字母表排列，而且在同一個字母的條件下，大寫比小寫要排前。於是我就用純C做了。
我的思路是構造兩個數組ch和val來儲存字母和字母的值，字母的值轉化成數值儲存，比如a是0.5， b是1.5，A是0，B是1，然後再從小到大排序，然後dfs前序遍歷輸出就是題目要求的輸出了。
但是，編完後發現一個很大的問題，在有重復字母的情況下會輸出重復的排列。。。
代碼如下（未AC）：
[cpp]
#include<stdio.h>
#include<string.h>
float val[13];
int num, res[13];
char ch[13];
void dfs(int cur)
{
if (cur == num)
{
for (int i = 0; i < num; i++)
printf("%c", ch[res[i]]);
printf("\n");
return;
}
for (int i = 0; i < num; i++)
{
int ok = 1;
res[cur] = i;
for (int j = 0; j < cur; j++)
if (res[j] == i)
{
ok = 0;
break;
}
if (ok)
dfs(cur + 1);
}
return;
}
int main()
{
int n;
num = 0;
scanf("%d", &n);
while (n--)
{
num = 0;
scanf("%s", ch);
for (int i = 0; ch[i] != '\0'; i++)
{
num++;
if (ch[i] >= 'A'&& ch[i] <= 'Z')
val[i] = ch[i] - 'A';
else
val[i] = ch[i] - 'a' + 0.5;
}
for (int i = 0; i < num; i++)
for (int j = i + 1; j < num; j++)
if (val[i] > val[j])
{
float e = val[i];
val[i] = val[j];
val[j] = e;
char t = ch[i];
ch[i] = ch[j];
ch[j] = t;
}
dfs(0);
}
return 0;
}
#include<stdio.h>
#include<string.h>
float val[13];
int num, res[13];
char ch[13];
void dfs(int cur)
{
if (cur == num)
{
for (int i = 0; i < num; i++)
printf("%c", ch[res[i]]);
printf("\n");
return;
}
for (int i = 0; i < num; i++)
{
int ok = 1;
res[cur] = i;
for (int j = 0; j < cur; j++)
if (res[j] == i)
{
ok = 0;
break;
}
if (ok)
dfs(cur + 1);
}
return;
}
int main()
{
int n;
num = 0;
scanf("%d", &n);
while (n--)
{
num = 0;
scanf("%s", ch);
for (int i = 0; ch[i] != '\0'; i++)
{
num++;
if (ch[i] >= 'A'&& ch[i] <= 'Z')
val[i] = ch[i] - 'A';
else
val[i] = ch[i] - 'a' + 0.5;
}
for (int i = 0; i < num; i++)
for (int j = i + 1; j < num; j++)
if (val[i] > val[j])
{
float e = val[i];
val[i] = val[j];
val[j] = e;
char t = ch[i];
ch[i] = ch[j];
ch[j] = t;
}
dfs(0);
}
return 0;
}
結果，剪枝剪了半天剪不了，果然我太弱了。。。
參考網上的解題報告，發現好多都是用的C++裡面的stl裡面的next_permutation函數，找到一個dfs的，照著剪枝，提交後老超時，我還以為是我手工排序比sort慢，又改又超時，改了幾次之後越來越像人家的代碼，後來干脆把他的代碼貼上去，也是超時！
好坑！
剪枝後代碼如下（未AC）：
[cpp]
#include<stdio.h>
#include<string.h>
float val[13];
int num, res[13], visited[13];
char ch[13];
void dfs(int cur)
{
if (cur == num)
{
for (int i = 0; i < num; i++)
printf("%c", ch[res[i]]);
printf("\n");
return;
}
for (int i = 0; i < num; i++)
if (!visited[i])
{
res[cur] = i;
visited[i] = 1;
dfs(cur + 1);
visited[i] = 0;
while(i + 1 < num && val[i] == val[i + 1])
i++;
}
}
int main()
{
int n;
num = 0;
scanf("%d", &n);
while (n--)
{
memset(visited, 0, sizeof(visited));
num = 0;
scanf("%s", ch);
for (int i = 0; ch[i] != '\0'; i++)
{
num++;
if (ch[i] >= 'A'&& ch[i] <= 'Z')
val[i] = ch[i] - 'A';
else
val[i] = ch[i] - 'a' + 0.5;
}
for (int i = 0; i < num; i++) //sort
for (int j = i + 1; j < num; j++)
if (val[i] > val[j])
{
float e = val[i];
val[i] = val[j];
val[j] = e;
char t = ch[i];
ch[i] = ch[j];
ch[j] = t;
}
dfs(0);
}
return 0;
}
#include<stdio.h>
#include<string.h>
float val[13];
int num, res[13], visited[13];
char ch[13];
void dfs(int cur)
{
if (cur == num)
{
for (int i = 0; i < num; i++)
printf("%c", ch[res[i]]);
printf("\n");
return;
}
for (int i = 0; i < num; i++)
if (!visited[i])
{
res[cur] = i;
visited[i] = 1;
dfs(cur + 1);
visited[i] = 0;
while(i + 1 < num && val[i] == val[i + 1])
i++;
}
}
int main()
{
int n;
num = 0;
scanf("%d", &n);
while (n--)
{
memset(visited, 0, sizeof(visited));
num = 0;
scanf("%s", ch);
for (int i = 0; ch[i] != '\0'; i++)
{
num++;
if (ch[i] >= 'A'&& ch[i] <= 'Z')
val[i] = ch[i] - 'A';
else
val[i] = ch[i] - 'a' + 0.5;
}
for (int i = 0; i < num; i++) //sort
for (int j = i + 1; j < num; j++)
if (val[i] > val[j])
{
float e = val[i];
val[i] = val[j];
val[j] = e;
char t = ch[i];
ch[i] = ch[j];
ch[j] = t;
}
dfs(0);
}
return 0;
}
我決定用STL了。。。
代碼如下（已A）：
[cpp]
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
bool cmp(char a, char b)
{
double t1 = a, t2 = b;
if (a >= 'A' && a <= 'Z')
t1 += 31.5;
if (b >= 'A' && b <= 'Z')
t2 += 31.5;
return t1 < t2;
}
int main()
{
int n, len;
char str[15];
cin >> n;
while(n--)
{
cin >> str;
len = strlen(str);
sort(str, str + len, cmp);
do
{
cout << str << endl;
}
while(next_permutation(str, str + len, cmp));
}
return 0;
}
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
bool cmp(char a, char b)
{
double t1 = a, t2 = b;
if (a >= 'A' && a <= 'Z')
t1 += 31.5;
if (b >= 'A' && b <= 'Z')
t2 += 31.5;
return t1 < t2;
}
int main()
{
int n, len;
char str[15];
cin >> n;
while(n--)
{
cin >> str;
len = strlen(str);
sort(str, str + len, cmp);
do
{
cout << str << endl;
}
while(next_permutation(str, str + len, cmp));
}
return 0;
}
