康托展开

康托展开

• 求一个数在其全排列的次序

• 规定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;
  }