[ cantor expansion ] 康托展开

給一個$0 \sim n-1$共$n$個數字的全排列，求他是排名第幾的全排列；給一個名次，求全排列。這東西可以有效的減少hash_table的大小。
以下附上code:

	#include<vector>
	#define MAXN 11
	int factorial[MAXN];
	inline void init(){
	factorial[0]=1;
	for(int i=1;i<=MAXN;++i){
	factorial[i]=factorial[i-1]*i;
	}
	}
	inline int encode(const std::vector<int> &s){
	int n=s.size(),res=0;
	for(int i=0;i<n;++i){
	int t=0;
	for(int j=i+1;j<n;++j){
	if(s[j]<s[i])++t;
	}
	res+=t*factorial[n-i-1];
	}
	return res;
	}
	inline std::vector<int> decode(int a,int n){
	std::vector<int> res;
	std::vector<bool> vis(n,0);
	for(int i=n-1;i>=0;--i){
	int t=a/factorial[i],j;
	for(j=0;j<n;++j){
	if(!vis[j]){
	if(t==0)break;
	--t;
	}
	}
	res.push_back(j);
	vis[j]=1;
	a%=factorial[i];
	}
	return res;
	}

view raw cantor_expansion.cpp hosted with ❤ by GitHub

使用前記得要呼叫init();