康托展开 和 逆康托展开 与排列与排名密切相关。
康托展开 被用来求一个排列的排名，时间复杂度 \(O(n\log n)\)。
假设我们要求排列 \(n=5,a[]=\{3,4,1,5,2\}\) 的排名。
定义 \(s[i]\) 表示在 \(a[i]\) 后面的数中，有多少个比 \(a[i]\) 要小。不难得到 \(s[]=\{2,2,0,1,0\}\)。
设原排列的排名是 \(k\)，则\[k=\sum_{i=1}^{n-1}({s[i]\times(n-i)!})\]
在上面的例子中，排名 \(k=61\)。代码实现较为简单，在此不给出代码。
逆康托展开 被用来求排名为 \(k\) 的排列，时间复杂度为 \(O(n\log n)\)。
假设我们要求排名为 \(k=61\) 的排列。
同样定义 \(s[i]\) 表示在 \(a[i]\) 后面的数中，有多少个比 \(a[i]\) 要小。逆康托展开能根据排名求出 \(s[]\) 数组，进而算出原排列。
算法流程
在上面的例子中，
61/4!=2...13，s[1]=2；
13/3!=2...1，s[2]=2；
1/2!=0...1，s[3]=0；
1/1!=1...0，s[4]=1；s[5]=0。
所以 \(s[]=\{2,2,0,1,0\}\)。
使用树状数组求出 \(a[]\) 数组即可。
原文：https://www.cnblogs.com/yhmaster/p/11818891.html