康托展开

定义即公式

康托展开表示的是全排列到自然数的映射，康托展开的本质即为某一全排列在整个全排列序列中的顺序。即1 3 2在由1,2,3三个数组成的全排列中的顺序为2。同时此项展开是一个可逆的过程，存在正向运算以及逆向运算。公式为：

X= a[n] * (n-1)! + a[n-1]*(n-2)!+ … +a[i] * (i-1)! + … + a[1] * 0!

其中a[i]为整数，并且 0<= a[i] < i, 1<= i <=n.
a[i]:设x为一串数字或字符串中第i个元素，a[i]即表示x之后的元素中比x小的元素的个数。
例如序列： 3 2 1
X=2 * 2！+1 * 1!+ 0 * 0!=5;

用途

由康托展开的公式可知：n位（0~n-1）全排列后，其康托展开唯一且最大约为n!，因此可以由更小的空间来储存这些排列。由公式可将X逆推出对应的全排列。因此康托展开多用于构建哈希表时的空间压缩。

例题代码

现在有”abcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？
输入 ：

每行输入一行字符串，保证是a~l这12个字符的某种排列
EOF结束

输出：

输出一个整数，代表这个排列排在第几位。
样例输入：
abcdefghijkl
abcdefghiklj
gfkedhjblcia

样例输出1：
0
3
260726925

代码：

c++

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
typedef long long ll;
ll ans;
string s;
int factorial(int i)
{
	if(i==0||i==1) return i;
	else
	{
		return i*factorial(i-1);
	}
 } 
int main()
{
	while(cin>>s){
		ans=0;
	for(int i=0;i<s.size();i++)
	{
		int tmp=0;
		for(int j=i+1;j<s.size();j++)
		{
			if(s[j]<s[i])
			{
				tmp++;
			}
		}
		ans+=factorial(s.size()-i-1)*tmp;
	}
	cout<<ans<<endl;
}
}

逆康托公式：即给出序号，输出排列：
代码：

c++

#include <bits/stdc++.h>
using namespace std;
int factor(int k){
	if(k == 0 || k == 1) return 1;
	return k * factor(k-1);
}
int ans[105], book[105];
int main(){
	int n, k, m, key, x, j;
	while(cin >> n >> m){
		memset(book, 0, sizeof book);
		--n;		
		for(int i = 1; i <=m;++i){
			k = factor(m-i);
			key = n/k+1;
			n %= k;			
			j = 1;	
			while(key){
				if(!book[j]) --key;
				++j;
			}
			ans[i] = j-1;
			book[j-1] = 1;
		}
		for(int i = 1; i <= m; ++i)
			printf("%d", ans[i]);
		printf("\n");
	}
	return 0;
}