再セット可能な符号化と復号化について

すなわちabbacdbの繰返し可能な文字列を組合せで辞書順に並べたシーケンス番号に変換したり、与えられたシーケンス番号と与えられた集合に基づいて復号したりして、符号化と復号の複雑さはいずれもO(n*k^2)であり、nは要素の個数であり、kは要素の種類である.
エンコーディング

int count[26];
int fac[13];

int code(char *s, int len)
{
	int ret = 0, limit = 0;
	memset(count, 0, sizeof(count));
	for(int i = 0; i < len; ++i)
	{
		++count[s[i]-'a'];
		limit = max(limit, s[i]-'a');
	}
	for(int i = 0; i < len; ++i)
	{
		for(int j = 0; j < s[i]-'a'; ++j)
			if(count[j])
			{
				int tret = fac[len-i-1];
				--count[j];
				for(int k = 0; k <= limit; ++k)
					tret /= fac[count[k]];
				++count[j];
				ret += tret;
			}
		--count[s[i]-'a'];
	}
	return ret;
}


char str[15];

int main()
{
	fac[0] = 1;
	for(int i = 1; i <= 12; ++i)
		fac[i] = i*fac[i-1];
	while(~scanf("%s", str))
	{
		printf("%d
", code(str, strlen(str))+1);
	}
	return 0;
}

デコード

int fac[13];
int count[26];
char ans[20];

char *decode(int num, int len)
{
	int temp;
	for(int i = 0; i < len; ++i)
	{
		int ind;
		for(ind = 0; ind < 26; ++ind)
			if(count[ind])
			{
				--count[ind];
				temp = fac[len-i-1];
				for(int k = 0; k < 26; ++k)
					temp /= fac[count[k]];

				if(temp < num)
					num -= temp;
				else
					break;
				++count[ind];

			}
		ans[i] = ind+'a';
	}
	ans[len] = '\0';
	return ans;
}

int main()
{
	fac[0] = 1;
	for(int i = 1; i <= 12; ++i)
		fac[i] = i*fac[i-1];
	int num;
	while(~scanf("%d", &num))
	{
		memset(count, 0, sizeof(count));
		char temp[2];
		int len = 0;
		while(~scanf("%s", temp))
		{
			scanf("%d", count+temp[0]-'a');
			len += count[temp[0]-'a'];
		}

		printf("%s
", decode(num, len));
	}
	return 0;
}