康托展开与逆康托展开

2019-11-08 20:09:17

字体：大中小

来源：转载

供稿：网友

康托展开

康托展开就是指当前n个元素的排列在这n个元素的全排列里的排名(从小到大) 逆康托展开就是已知某排列在全排列的排名，求这个排列

那么对于n个数来说，康托展开为：，在这个公式中an表示第i个元素在未出现的元素中排第几。如：对于507来说，5在507中排第1（从0开始），0在07中排第0,7排第0即a3=1,a2=0,a1=0，这样得到507在所有排列中ans=2(从零开始)

代码实现：

ll h[maxn]; //阶乘数组void init(int n){ h[0] = 1; for(ll i=1;i<n;i++) h[i] = h[i-1]*i;}ll slove(char a[]){ //康托定理 int len = strlen(a); ll res = 0; for(int i=0;i<len;i++) { int tmp = 0; for(int j=i+1;j<len;j++) { if(a[i]>a[j]) tmp++; } res += tmp*h[len-i-1]; } return res;}

逆康托展开

void slove(ll n,ll m){ n--; vector<int> v; vector<int> a; for(int i=1;i<=m;i++) v.push_back(i); for(int i=m;i>=1;i--) { LL r = n % f[i-1]; LL t = n / f[i-1]; n = r; sort(v.begin(),v.end()); a.push_back(v[t]); v.erase(v.begin()+t); } vector<int>::iterator it; for(it = a.begin();it != a.end();it++) cout<<*it; cout<<endl; }

上一篇：07 抓包分析

下一篇：20170215C语言提升08_指针_02数组指针及指针数组及函数指针