算法_康托展开

本文主要是介绍算法_康托展开，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Def

康托展开是一个全排列到一个自然数的双射。实质是计算当前全排列在所有有小到大全排列中的顺序，可逆。

公式： X = A_n (n - 1)! + A_{n - 1} (n - 2)! + ··· + A₁· 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;
}

这篇关于算法_康托展开的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！