康托展开

求一个数在其全排列的次序
规定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;
}