浅谈康托展开与其逆.

## 康托展开 ### What's this? 　来自[度娘](https://baike.baidu.com/item/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80/7968428?fr=aladdin)的解释： > 康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。 概念应该不是很好理解,所以这里直接给出作用. 这里的解释与网络上的不同,但是做题的时候是对的,这里请大家不要喷 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$ 这里的话,与网上的有些不同,这里通过公式直接求出来的就是排名.不过这个排名和网络上的其他讲解不太相同。 这里还有[度娘](https://baike.baidu.com/item/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80/7968428?fr=aladdin)的讲解.不过和我的理解不太一样. ``代码`` ```c++ 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｝。 式子的话,**先除后模**就好了 ``代码`` ```c++ 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](https://www.luogu.org/problemnew/show/P3014)　[p2524 Uim的情人节礼物·其之弐](https://www.luogu.org/problemnew/show/P2524)