笔记
康托展开和逆康托展开
康托展开表示的就是是当前排列组合在n个不同元素的全排列中的名次
逆康托展开则是由名次得出该名次的排列组合
公式：康托展开值X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!
X表示该排列组合前面有X个排列组合，所以该排列组合是第X+1个
a[i]表示当前未用到的元素中该元素排第几个
//阶乘 static const int Fac[]={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; //康托展开 int cantor(int *a,int n){ int x=0; for(int i=0;i<n;++i){ int cnt=0; for(int j=i+1;j<n;++j) if(a[j]<a[i])cnt++; x+=Fac[n-i-1]*cnt; } return x; } //逆康托展开 void decantor(int x,int n){//x为康托展开值，n为元素个数 vector<int>v;//存放当前可选数 vector<int>a;//所求排列组合 for(int i=1;i<=n;++i)v.push_back(i); for(int i=n;i>=1;--i){ int l=x%Fac[i-1]; int r=x/Fac[i-1]; x=l; a.push_back(v[r]); v.erase(v.begin()+r); } }