康托展开

康托展开表示的是当前排列在n个不同元素的全排列中的名次。比如213在这3个数所有排列中排第3。

那么，对于n个数的排列，康托展开为：

其中表示第i个元素在未出现的元素中排列第几。举个简单的例子：

对于排列4213来说，4在4213中排第3，注意从0开始，2在213中排第1，1在13中排第0，3在3中排第0，即：

，得到的ans是比原数小的数，要得到第几个数应该加一。

代码实现：

#include<stdio.h>
#include<string.h>
int fac(int x)
{
    if(x==0)return 0;
    if(x==1)return 1;
    return x*fac(x-1);
}
int Cantor(char *str)
{  
    int n,i,j,s;
    int ans=0;
    n=strlen(str);
    for(i=0;i<n;i++)
    {
        s=0;
        for(j=i+1;j<n;j++)
        if(str[j]<str[i])
        s++;
        ans=ans+s*fac(n-i-1);
    }
    return ans+1;           //返回该字符串是全排列中第几大，从1开始
}
int main()
{
    int ans;
    char a[100]={0};
    gets(a);
    ans=Cantor(a);
    printf("%d",ans);
    return 0;
}

通过康托逆展开生成全排列

如果已知 s = [“A”, “B”, “C”, “D”]，X(s1) = 20，能否推出 s1 = [“D”, “B”, “A”, “C”] 呢？

首先要减一。
　　因为已知 X(s1) = a43! + a32! + a21! + a10! = 20，所以问题变成由 20 能否唯一地映射出一组 a4、a3、a2、a1？如果不考虑 ai 的取值范围，有
33! + 12! + 01! + 00! = 20
23! + 42! + 01! + 00! = 20
13! + 72! + 01! + 00! = 20
03! + 102! + 01! + 00! = 20
03! + 02! + 201! + 00! = 20
等等。但是满足 0 <= ai <= n-1 的只有第一组。可以使用辗转相除的方法得到 ai，如下图所示：

知道了a4、a3、a2、a1的值，就可以知道s1[0] 是子数组[“A”, “B”, “C”, “D”]中第3大的元素 “D”，s1[1] 是子数组 [“A”, “B”, “C”] 中第1大的元素”B”，s1[2] 是子数组 [“A”, “C”] 中第0大的元素”A”，s[3] 是子数组 [“C”] 中第0大的元素”C”，所以s1 = [“D”, “B”, “A”, “C”]。

代码实现：

#include<stdio.h>
#include<string.h>
int fac(int x)
{
    if(x==0)return 0;
    if(x==1)return 1;
    return x*fac(x-1);
}
void reCantor(char str[100],int temp)
{
    int n=strlen(str);
    int x,i,j;
    for(i=0;i<n-1;i++)
    {
        x=temp/fac(n-1-i);
        printf("%c",str[x]);
        for(j=x;j<n-i;j++)
            str[j]=str[j+1];
        temp=temp%fac(n-1-i);
    }
    printf("%c",str[0]);
    printf("\n");
}
int main()
{
    int temp;
    char a[100]={0};
    gets(a);    //如果有需要的话，先把数组a从小到大排列好 
    scanf("%d",&temp);
    temp--;
    reCantor(a,temp);
    return 0;
}