康托展开及其逆运算实现|康托展开及其逆运算实现 C++

2021-12-12

康托展开康托展开

求一个数在其全排列的次序
【康托展开及其逆运算实现|康托展开及其逆运算实现 C++】规定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 a; while(num!=0){ a.push_back(num%10); num/=10; } for(int i=0; i=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=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; }

推荐阅读

上一篇：《她的城》

下一篇：带娃几个月的妈妈给准妈妈的经验之谈