POJ_1256 Anagram

勉強する気がおきない。

問題
単語が与えられる。辞書式配列で、並び替えたものをすべて列挙せよ。
重複はだめ。
解法
やるだけ。
辞書の順序が
AaBbCc...Zzとなっているのでこれに注意し、文字<->数値の変換用配列を作っておくと便利。
重複がダメなので、使った文字を覚えておかないといけない。

実装

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_STRLEN = 100;
int a2i[128];
char i2a[26 * 2];

char string[MAX_STRLEN];//文字列
int s_len;		//文字列長
bool used[MAX_STRLEN];	//文字を使用したかのフラグ

void init(){
	for(int i = 0; ; i++){
		a2i['A' + i] = i * 2;
		i2a[i * 2] = 'A' + i;
		a2i['a' + i] = i * 2 + 1;
		i2a[i * 2 + 1] = 'a' + i;
		if('A' + i == 'Z')
			break;
	}
}
char anagram[MAX_STRLEN];
void g(int n){
	if(n == s_len){
		anagram[n] = 0;
		printf("%s\n", anagram);
		return;
	}
	bool used_num[26 * 2];	//同じ文字列を重複して作らないため
	fill(used_num, used_num + 26 * 2, false);
	for(int i = 0; i < s_len; i++){
		if(used_num[string[i]] || used[i]) continue;
		used_num[string[i]] = true;

		used[i] = true;
		anagram[n] = i2a[string[i]];
		g(n + 1);
		used[i] = false;
	}
}
int main(){
	int n;
	char c;
	init();
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%s", string);
		scanf("%c", &c);
		s_len = strlen(string);
		for(int j = 0; j < s_len; j++)
			string[j] = a2i[string[j]];
		sort(string, string + s_len);
		fill(used, used + MAX_STRLEN, false);
		g(0);
	}
	return 0;
}