康托展開
康托展開
求一個數(shù)在其全排列的次序
規(guī)定
a[n]為 在第n位后面且比其數(shù)值小的數(shù)字個數(shù)與(n-1)!的乘積，則此數(shù)次序為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; }
逆運(yùn)算
通過在全排列中的次序求出這個數(shù)
先自減一作為第一輪的被除數(shù)，從第1位到第
n-1位依次循環(huán)，被除數(shù)除以(n-1)!，設(shè)其商數(shù)為m掠手，余數(shù)為r，則這個數(shù)的第n位是數(shù)組a[1..n]還未被標(biāo)記中第m+1小的數(shù)字狸捕，標(biāo)記這個數(shù)字喷鸽，r作為下一輪的被除數(shù)；第n位即最后數(shù)組a[1..n]還未被標(biāo)記的數(shù)字-
例碼
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; }
