康托展开和逆康托展开

康托展开和逆康托展开

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 smaller = 0;  // 在当前位之后小于其的个数
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[i])
                smaller++;
        }
        x += FAC[n - i - 1] * smaller; // 康托展开累加
    }
    return x;  // 康托展开值
}

int  fac[] = {1,1,2,6,24,120,720,5040,40320};
//康托展开的逆运算,{1...n}的全排列，中的第k个数为s[]
void reverse_kangtuo(int n,int k,char s[])
{
    int i, j, t, vst[8]={0};
    k--;
    for(int i=0;i<n;i++){
        t = k/fac[n-i-1];
        for(int j=1;j<=n;j++){
            if(!vst[j]){
                if(t==0) break;
                t--;    
            }
        }
        s[i] = '0'+j;
        vst[j] = 1;
        k%=fac[n-i-1];
    }
}