https://blog.csdn.net/tenkuo/article/details/153918962

康托展开与逆康托展开实现

程序实现了康托展开（将排列转化为字典序排名）和逆康托展开（将排名转化为排列），并处理多组查询。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[21],n,m;

LL d[21];
LL  kangtuo()//把排列转化为整数：n个数的排列a是第几个排列（a排列的字典序）
{
    bool bo[21];memset(bo,0,sizeof(bo));
    LL sum=0;
    for(int i=1;i<=n;i++)
    {
        int k=0;for(int j=1;j<a[i];j++)k=k+(bo[j]==0);//统计有多少个比a[i]小且没有出现过的数
        sum=sum+k*d[n-i];
        bo[a[i]]=1; 
    }
    return sum+1;//sum表示a排列之前有多少个排列   
}
void nikangtuo(LL sum)//把整数转化为排列
{
    sum--;
    bool bo[21];memset(bo,0,sizeof(bo));
    for(int i=1;i<=n;i++)
    {
        int k=sum/d[n-i];
        sum=sum%d[n-i];
        int kk=0;
        for(int j=1;j<=n;j++)
        {
            if(bo[j]==0)
            {
                kk++;
                if(kk==k+1){a[i]=j;bo[j]=1;break;}
            }   
        }
    }
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
    printf("\n");
}
int main()
{
    d[0]=1;for(int i=1;i<=20;i++)d[i]=d[i-1]*i;
    cin>>n>>m;
    while(m--)
    {
        char c;cin>>c;
        if(c=='P')
        {
            LL sum;scanf("%lld",&sum);
            nikangtuo(sum);
        }
        else{
            for(int i=1;i<=n;i++)scanf("%d",&a[i]);
            printf("%lld\n",kangtuo());
        }
    }
    return 0;
}