python/TangDou/AcWing/KangTuo/Cantor.cpp

#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;
}