康托展开
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_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\)提高组第四题