笔记

康托展开和逆康托展开

康托展开和逆康托展开（转） - Sky丨Star - 博客园 (cnblogs.com)

康托展开表示的就是是当前排列组合在n个不同元素的全排列中的名次

逆康托展开则是由名次得出该名次的排列组合

公式：康托展开值X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!

X表示该排列组合前面有X个排列组合，所以该排列组合是第X+1个

a[i]表示当前未用到的元素中该元素排第几个

//阶乘
static const int Fac[]={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
//康托展开
int cantor(int *a,int n){
    int x=0;
    for(int i=0;i<n;++i){
        int cnt=0;
        for(int j=i+1;j<n;++j)
            if(a[j]<a[i])cnt++;
        x+=Fac[n-i-1]*cnt;
    }
    return x;
}
//逆康托展开
void decantor(int x,int n){//x为康托展开值，n为元素个数
    vector<int>v;//存放当前可选数
    vector<int>a;//所求排列组合
    for(int i=1;i<=n;++i)v.push_back(i);
    for(int i=n;i>=1;--i){
        int l=x%Fac[i-1];
        int r=x/Fac[i-1];
        x=l;
        a.push_back(v[r]);
        v.erase(v.begin()+r);
    }
}