第k个排列数:康托展开

第k个排列数:康托展开

序列中各个元素都不相同,将这个序列进行全排列,并且将所有排列从小到大排序。现在给定一个序列,确定这是第几个排列。以及它的逆问题:确定第k个排列是什么。这可用Cantor展开以及逆Cantor展开。 康托展开是一个全排列到一个自然数的双射,常用于构建hash表时的空间压缩。

例如,[1, 2, 3, 4] 共有4!种排列,1234,1243,1324,2431,3412,4321等等。按顺序应该是1234, 1243, 1324, 1342, 1423, 1432等等。虽然可以通过C++ STL的next_permutation(begin, end);来算下一个全排列,理论上你要算n个数的第k个排列只要调用k-1次next_permutation()就行,但是因为next_permutation的时间复杂度是O(n),要调用多次next_premutation才能算出第k个排列,效率不够高。

而康托展开只要O(n)的时间就可以计算出这个序列是第几个排列,a[N],a[N-1],..,a[2],a[1]的排列的序数X为:

其中p[k]表示a[k]到a[1]中小于a[k]的个数。

举个例子来说,判断34152是12345的第几个排列数。即a[5]=3,a[4]=4,a[3]=1,a[2]=5,a[1]=1。首先得到各个p[i]:

p[5]是其后小于3的数量,只有1和2,所以p[5]为2。p[4]是4之后各位小于4的个数,为2。类似地,p[3]=0,p[2]=1,p[1]=0

这样,X= p[5]*4! + p[4]*3! + p[3]*2! + p[2] * 1! +p[1] * 0! = 48+12+1 = 61,说明这个序列34152是12345的排列中第62小的序列

反过来就是逆康托展开。

通过排列数X,对其与各个阶乘取余可得到p[i]。第X个排列的第i位则可以通过当前未使用过的数中选出第p[i]个数字确定。


#include <cstdio>
#include <cstring>
#define MAXN 20

int fact(int x)
{
    int t=1;
    for(int i=1;i<=x;i++)
    {
        t*=i;
    }
    return t;
}

int anticantor(int x,int n)
{
    int p[MAXN],r[MAXN],used[MAXN];
    int N=n; 
    int M =x;
    int i = 0;
    while(N>0)
    {
        p[i]=M/fact(N-1);
        M%=fact(N-1);
        N--;
        i++;
    }
    N=i;
    memset(used,0,sizeof(used));
    for(i=0;i<N;i++)
    {
        r[i]=1;
        int skip = p[i]+1;
        while(1)
        {
            if(used[r[i]]==0)
            {
                skip -=1;
            }
            if(skip==0)
            {
                break;
            }
            r[i]++;
        }
        used[r[i]]=1;
    }
    int res = 0;
    for(int i=0;i<N;i++)
    {
        res = res*10 + r[i];
    }
    return res;
}

int cantor(int x)
{
 
    char a[MAXN];
    int p[MAXN];
    int i,N ;
    sprintf(a,"%d",x);
    for(i=0;a[i];i++)
    {
        a[i]=a[i]-'0';
    }
    N=i;
    for(i=0;i<N;i++)
    {
        p[i] =0;
        for(int j=i+1;j<N;j++)
        {
            if(a[j]<a[i])
            {
                p[i]++;
            }
        }
    }
    int X=0;
    for(i=0;i<N;i++)
    {
        X+=p[i]*fact(N-i-1);
    }
    return X; 
    
}

int main(void)
{
    int N;
    scanf("%d",&N);
    printf("%d\n",cantor(N));
    printf("%d\n",anticantor(cantor(N),5));
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注