Anagram 구하기(철자바꾸기) 알고리즘

아래는 직접 구현한 소스이다.

원리는 string 내에 각 알파벳이 몇 개 있는지 카운트한 뒤, 차례대로 알파벳들을 하나씩 추가해가며 anagram들을 만든다.

이 때 같은 알파벳이 여러개 있는 경우에는 그 알파벳들이 들어갈 수 있는 위치를 조합(Combination)으로 구해 그 위치에만 넣는다.

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>

using namespace std;
void comb(int num, int maxnum, int left, vector<int>& res, string str, vector<string>& cont, char c)//1부터 maxnum까지의 숫자 중 num개를 뽑은 조합
{
	if (left == 0)
	{
		int len = res.size();
		string newstr = str;
		string tmpstr(1, c);
		for (int i = len-1; i >=0; i--)
		{
			newstr.insert(res[i], tmpstr);
		}
		cont.push_back(newstr);
		return;
	}
	
	if (left == num)
	{
		for (int i = 0; i <= maxnum; i++)
		{
			res.push_back(i);
			comb(num, maxnum, left - 1, res, str, cont, c);
			res.pop_back();
		}
	}
	else
	{
		for (int i = res.back(); i <= maxnum; i++)
		{
			res.push_back(i);
			comb(num, maxnum, left - 1, res, str, cont, c);
			res.pop_back();
		}
	}
}

vector<string> anagram(string str)
{
	vector<string> res;
	vector<string> newres;
	vector<int> temp;
	int LetterCount['z' - 'a' + 5];
	for (int i = 0; i < 'z' - 'a' + 5; i++) LetterCount[i] = 0;
	for (int i = 0, len = str.size(); i < len; i++)
	{
		LetterCount[str[i]-'a']++;
	}
	//for (int i = 0; i < 'z' - 'a' + 5; i++) printf("%d ", LetterCount[i]); puts("");
	for (char ch = 'a'; ch <= 'z'; ch++)
	{
		newres.clear();
		if (LetterCount[ch - 'a'] != 0 && res.empty())
		{
			string init;
			for (int i = 0; i < LetterCount[ch - 'a']; i++) init += string(1, ch);
			res.push_back(init);
			continue;
		}
		for (auto it = res.begin(); it != res.end(); it++)
		{
			comb(LetterCount[ch - 'a'], it->;size(), LetterCount[ch - 'a'], temp, *it, newres, ch);
		}
		res = newres;
	}
	return res;
}

int main()
{
	string a;
	while (true)
	{
		cin >> a;
		vector<string> c = anagram(a);
		for (auto it = c.begin(); it != c.end(); it++) 
			cout << *it << endl;
		cout << "Cnt : " << c.size() << endl;
	}
}

다음은 STL의 next_permutation으로 구현한 소스이다.

시간복잡도는 k = string.size(), m = anagram의 수 일 때 정렬에 O(k log k), next_permutation에 O(mk)이다.

즉 위의 소스보다 더 좋다...

vector<string> anagram(string str)
{
	vector<string> res;
	sort(str.begin(), str.end());
	do	{
		res.push_back(str);
	} while (next_permutation(str.begin(), str.end()));
	return res;
}//main은 생략