You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

34 lines
1.1 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
// 阶乘表
int fact[20];
void init_fact(int n) {
fact[0] = 1; // 0的阶乘为1
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
}
// 康托展开
int cantor(string str) {
int x = 1; // 注意,因为 12345 是算作0开始计算的最后结果要把12345看作是第一个
int len = str.size();
for (int i = 0; i < len; i++) {
int smaller = 0; // 在当前位之后小于其的个数
for (int j = i + 1; j < len; j++)
if (str[i] > str[j]) smaller++;
// 两种方法:
// ① 往后看计算str[i]是第几大的数,或者说计算有几个比他小的数
// ② 往前看,计算出现了几个比自己小的数,从自己身上扣除掉逆序数量,也就是后面剩余比自己小的数量
x += smaller * fact[len - i - 1]; // 乘上阶乘
}
return x;
}
int main() {
// 初始化10以内的阶乘表
init_fact(10);
string str = "52413";
// 康托展开
cout << cantor(str) << endl;
return 0;
}