康托展开
应用
已知一个字符串, 求其字典序
公式
|
|
原理
康托展开实际是求在当前序列之前有几种字典序
对于[D, B, A, C]
以D为开头的序列之前必定有以A、 B、 C(字典序比D小)开头的序列,共有3种, 每种有3!种可能性 所以 a4 = 3 * 3!
以B为开头的序列之前必定有以A(字典序比B小)开头的序列,共有2种, 每种有2!种可能性 所以 a3 = 1 * 2!
以A为开头的序列之前必定无序列,共有0种(因为在子串AC中, 无其他元素比A的字典序更小), 每种有1!种可能性 所以 a2 = 0 * 1!
同理 a1 = 0 * 0!
代码实现
|
|
康托逆展开
原理
如何求出ABCD的字典序为20的序列?
利用辗转相除法即可从字典序逆展开的得到an 到 a1
代码
|
|