浅谈康托展开与其逆.

2018-10-13 20:26:35


康托展开

What's this?

 来自度娘的解释:

康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。

概念应该不是很好理解,所以这里直接给出作用.

这里的解释与网络上的不同,但是做题的时候是对的,这里请大家不要喷 qwq

Function

 康托展开的作用是求n个数的全排列中某一个序列在所有排列中的次序(该排列次序(亦称之为排名)以字典序从小到大排序)

栗子

不理解的话还是来看下栗子好了.

Q:求在 $n=3$ 的全排列中{1,3,2}的排第几位.

A: 这很简单,我们可以写出 $n=3$ 的全排列再去看排名

{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}

很容易看出{1,3,2}的排名为第二名.

不理解的话还是自己手跑大样例.如果你不嫌累的话

这样写是为了自己好写,好理解些.

注意:康托展开应该是从排名为 $0$ 开始计数的。

深入

如果说,给我们的 $n$ 很大怎么办?

这时候就用到了康托展开.

考虑到 $n$ 的全排列会有 $n!$ 种,很明显,我们需要用到阶乘.

这里可能会有些解释不清楚.请大家见谅。

我们对于某一个排列,其排名肯定会与后边的排列有关。

即{1,5,3,4,2}的排名会与{5,3,4,2}有关,而{5,3,4,2}又会与{3,4,2}相关......

所以这里会用到阶乘

这里给出公式:

$$X=a_1 \times (n-1)! +a_2 \times(n-2)!+\dots +a_n \times 0!$$

定义:

  • $X$ 代表当前排列的排名。
  • $a_i$ 代表当前排列里从 $i$ 位置向右比 $i$ 位置的数小的数的个数.

栗子:在 $n=5$ 的全排列中,计算{3,4,1,5,2}的康托展开值。

首位是 $3$ ,我们用眼睛观察发现后面比 $3$ 小的数有两个.则 $a_1=2$

第二位是 $4$ ,发现后面比 $4$ 小的数有两个,注意这里 $3$ 是没有贡献的,它在 $4$ 的前面,则 $a_2=2$

第三位是 $1$ ,后面没有比 $1$ 小的数,则 $a_3=0$

第四位是 $5$ ,同样,后面比 $5$ 小的数只有 $1$ 则 $a_4=1$

第五位是 $2$ ,后面没有数了则 $a_5=0$

因此我们可以算出 $$X=2 \times (5-1)!+ 2\times (5-2)!+0 \times(5-3)!+1 \times (5-4)!+0\times (5-5)!=61$$ 所以从零开始计数的话我们算出的{3,4,1,5,2}的排名为 $61$

从一开始计数的话我们算出的排名则要 $+1$ 为 $62$

这里的话,与网上的有些不同,这里通过公式直接求出来的就是排名.不过这个排名和网络上的其他讲解不太相同。

这里还有度娘的讲解.不过和我的理解不太一样.

代码

int Contor(char s[],int n)
{
    int ans=0;
    for(R int i=0;i<n;i++)
    {
        int smaller=0;
        for(R int j= i+1 ;j<n;j++)
        {
            if(s[i] > s[j])smaller++;
        }
        ans += smaller*fac[n-i-1];
    }
    return ans+1;
}

逆康托展开

What?

什么?这玩意还能逆推?

当然.我们既然知道了这种式子,就肯定能倒推出来原排列啊 emm.

由于康托展开是一个双射.我不知道是啥

所以我们可以逆推回来

栗子

在 $n=5$ 的全排列中,给出 $61$ ,我们可求{3,4,1,5,2}

这里给出的排名一般是从 $0$ 开始计算的.

这里给出求解过程

用 $61÷4! = 2$ 余 $13$ ,说明 $a_1=2$ ,说明比第一位数小的数有 $2$ 个,所以第一位填 $3$ 。

用 $13÷3! = 2$ 余 $1$ ,说明 $a_2=2$ ,说明在第二位后面小于第二位的数有 $2$ 个,所以第二位为 $4$ 。

用 $1÷2! = 0$ 余 $1$ ,说明 $a_3=0$ ,说明在第三位后面没有小于第三位的数,所以第三位为 $1$ 。

用 $1÷1! = 1$ 余 $0$ ,说明 $a_4=1$ ,说明在第二位之后小于第四位的数有 $1$ 个,所以第四位为 $5$ 。

最后一位就是剩下的 $2$ 啦。

通过以上分析,所求排列为{3,4,1,5,2}。

式子的话,先除后模就好了

代码

void DeCantor(int x,int n)
{
    memset(use,0,sizeof use);
    x--;//这里从0开始计数,因此--.
    int j;
    for(R int i=1;i<=n;i++)
    {
        int t=x/fac[n-i] ;//求后面有几位比当前位小
        for(j=1;j<=n;j++)
         {
            if(!use[j])
            {
                if(!t)break;
                t--;
           }
        }
        printf("%d ",j);
        vis[j]=1;
        x%=fac[n-i];
    }
}

应用的话,见 $2018\ Noip$ 提高组初赛四.4

还有这两个例题p3014 [USACO11FB]牛线 Cow Line p2524 Uim的情人节礼物·其之弐