Def
康托展开是一个全排列到一个自然数的双射。实质是计算当前全排列在所有有小到大全排列中的顺序，可逆。
公式： X = An (n - 1)! + An - 1 (n - 2)! + ··· + A1· 0!
eg: [5 2 4 1 3]是序号几
①首位为5：当首位取1或2或3或4时，剩下的数不论怎么排都比52143小，排法有 4 * 4！种；
②固定首位5 _ _ _ _ ：看第二位，剩下1 2 3 4中比2小的就一个，排法有 1 * 3！种；
③固定5 2 _ _ _：看第三位，剩下1 3 4中比4小的有两个，排法有 2 * 2！种；
④固定5 2 4 _ _：剩下 1 3，0 * 1！种；
⑤固定5 3 4 1 _: 0 * 0！种。
综上：4 * 4！+ 1 * 3！+ 2 * 2！+ 0 * 1！+ 0 * 0！= 106
由于从0开始计数，所以52413的序号为107
从0开始计数的原因：按照上面的算法，12345为 0 * 4！+ 0 * 3！+ 0 * 2！+ 0 * 1！+ 0 * 0！= 0，但12345的序号为1。
代码
/***** 这里以字符串进行展示 字符串可泛化性好 ******/ #include<iostream> using namespace std; /*******打出0到9的阶乘表*******/ int f[20]; void jie_cheng() { f[0] = f[1] = 1; // 0的阶乘为1 for(int i = 2; i <= 9; i++) f[i] = f[i - 1] * i; } /**************康托展开****************/ int cantor(string str) { int ans = 1; //注意，因为 12345 是算作0开始计算的，最后结果要把12345看作是第一个 int len = str.length(); for(int i = 0; i < len; i++){ int tmp = 0;//用来计数的 for(int j = i + 1; j < len; j++){ if(str[i] > str[j]) tmp++; //计算str[i]是第几大的数，或者说计算有几个比它小的数 } ans += tmp * f[len - i - 1]; } return ans; } int main() { jie_cheng(); string str; cin >> str; cout<<cantor(str)<<endl; }