『算法-ACM 竞赛-数学-数论』康托展开与逆康托展开模板

ACM 常用模板合集

#include<bits/stdc++.h>

using namespace std;
const int MAX = 13;
int Fac[MAX],N;
//求出阶乘
void init(){
    Fac[0] = 1;
    for(int i=1;i<=N;++i){
        Fac[i] = Fac[i-1]*i;
    }
}
//康托展开
int Cantor(int *x){
    int res = 0;
    for(int i=1;i<=N;++i){
        int Count = 0;
        for(int j=i+1;j<=N;++j){
            if(x[j] < x[i])
                Count++;
        }
        res += Fac[N-i]*Count;
    }
    return res;
}
//逆康托展开
void DeCantor(int pos,int *x){
    set<int> st;
    for(int i=1;i<=N;++i){
        st.insert(i);
    }
    for(int i=1;i<=N;++i){
        int r = pos / Fac[N-i];
        int l = pos % Fac[N-i];
        pos = l;
        set<int>::iterator it;
        int Count = 0;
        for(it = st.begin();it != st.end();++it){
            Count++;
            if(Count == r+1){
                break;
            }
        }
        x[i] = *it;
        st.erase(it);
    }
}
int main(void){
    int x[MAX],pos;
    cin >> N;
    init();
    cin >> pos;
    DeCantor(pos,x);
    cout << "DeCantor:" << endl;
    for(int i=1;i<=N;++i){
        cout << x[i] << " ";
    }
    cout << endl;
    cout << "Cantor:" << endl;
    cout << Cantor(x) << endl;
    return 0;
}

风格 2：

void init(){
    Fac[0] = 1;
    for(int i=1;i<=N;++i){
        Fac[i] = Fac[i-1]*i;
    }
}

int kangtuo(int n,char a[])
{
    int i,j,t,sum;
    sum=0;
    for( i=0; i<n ;++i)
    {
        t=0;
        for(j=i+1;j<n;++j)
            if( a[i]>a[j] )
                ++t;
        sum+=t*fac[n-i-1];
    }
    return sum+1;
}
void reverse_kangtuo(int n,int k,char s[])
{
    int i, j, t, vst[8]={0};
    --k;
    for (i=0; i<n; i++)
    {
        t = k/fac[n-i-1];
        for (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];
    }
}