康托展开
康托展开
求一个数在其全排列的次序
规定
a[n]为 在第n位后面且比其数值小的数字个数与(n-1)!的乘积，则此数次序为a[1..n]的总和+1；比如52341的次序为(4*4!+1*3!+1*2!+1*1!+0*0!)+1-
例码
int fac(int t){ if(t==0) return 0; if(t==1) return 1; return fac(t-1)*t; } int cantor(int num){ int ans=0; vector <int> a; while(num!=0){ a.push_back(num%10); num/=10; } for(int i=0;i<a.size();i++){ int cnt=0; for(int j=i-1;j>=0;j--) if(a[i]>a[j]) cnt++; ans+=fac(i)*cnt; } return ans+1; }
逆运算
通过在全排列中的次序求出这个数
先自减一作为第一轮的被除数，从第1位到第
n-1位依次循环，被除数除以(n-1)!，设其商数为m，余数为r，则这个数的第n位是数组a[1..n]还未被标记中第m+1小的数字，标记这个数字，r作为下一轮的被除数；第n位即最后数组a[1..n]还未被标记的数字-
例码
int fac(int t){ if(t==0) return 0; if(t==1) return 1; return fac(t-1)*t; } int get_from_cantor(int num, int len){ num--; int m=1,ans=0; bool *book = new bool[len+1]; for(int i=1;i<len+1;i++) book[i]=1; for(int i=len;i>=2;i--){ int t=fac(i-1); m=num/t+1; while(book[m]==0){ m++; } book[m]=0; ans*=10; ans+=m; num%=t; } m=1; while(book[m]==0){ m++; } ans*=10; ans+=m; delete [] book; return ans; }
