Zhao70's Blog

CantorExpansion

康托展开

应用

已知一个字符串, 求其字典序

公式

1
2
X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!
//其中a[i]为当前未出现的元素中是排在第几个(从0开始)。

原理

康托展开实际是求在当前序列之前有几种字典序
对于[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!

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
\\注意: 因为排列可能数目众多,所以使用long long
long long contor(string & s)
{
long long ans = 0;
for(long long loc = 0; loc <= s.length() - 1; loc++)
{
string sub = s.substr(loc);
sort(sub.begin(), sub.end());
long long val = lower_bound(sub.begin(), sub.end(), s[loc]) - sub.begin();
ans = ans + fact(s.length() - 1 - loc) * val;
}
return ans;
}

康托逆展开

原理

如何求出ABCD的字典序为20的序列?

利用辗转相除法即可从字典序逆展开的得到an 到 a1
"康托逆展开"

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
string invcontor(long long val, string& s)
{
sort(s.begin(), s.end());
std::vector<long long> poly;
for(long long i = 0; i != s.length(); i++)
{
poly.push_back(val / fact(s.length() - 1 - i));
val = val % (fact(s.length() - 1 - i));
}
string ans;
for(long long i = 0; i < poly.size(); i++)
{
//cout << poly[i] << endl;
//cout << s << endl;
ans = ans + s[poly[i]];
s.erase(poly[i], 1);
}
return ans;
}

代码

github

参考链接

zhongkeli的专栏