第k个排列数:康托展开

第k个排列数:康托展开

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

例如,N=4的不重复序列\( (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),要调用多次才能算出第k个排列,效率不够高。

而康托展开只要O(n)的时间就可以计算出这个序列是第几个排列。

\( (a_n,a_{n-1},..,a_2,a_1) \) 排列在n!个阶乘中的序数X为:

\[ X=\sum_{k=1}^{N} (p_{k} \times ((k-1)!)) \]

其中\( 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 是\( (a_5,…,a_1) \)中小于\( a_5 =3 \)的数量,只有1和2满足所以\( p_5 =2 \)。\(p_4 \)是\( (a_4,…,a_1)\)中小于\( a_4=4 \) 的个数,为2。类似地,\( p_3=0 ,p_2 =1,p_1 =0 \)

这样,
\[\begin{align}X &= p_5\cdot4! + p_4 \cdot 3! + p_3 \cdot 2! + p_2 \cdot 1! +p_1 \cdot 0! \\
&= 2\cdot4! + 2 \cdot 3! + 0 + 1 \cdot 1! +0\\
&= 48+12+1 = 61 \end{align} \],说明这个序列34152是12345的排列中第62小的序列

康托展开的的逆过程,即由一个\( [0,n!-1] \)中的正整数m转换为长为n的全排列,可参阅 《 序数法:一种排列的生成算法

#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 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));
    return 0;
}

发表回复

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