【數學|算法】康託展開(Cantor expansion)及逆康託展開

康託展開(Cantor expansion)及逆康託展開
康託展開康託展開的定義

康託展開是一個全排列到一個自然數的雙射，常用於構建哈希表時的空間壓縮。康託展開的實質是計算當前排列在所有由小到大全排列中的順序，因此是可逆的。

應用方面：求集合全排列中某一狀態的字典序

例如，給定集合Set={1,2,3}, 需要求排列213的字典序大小。易得，在Set的全排列中， 有123、132兩個排列小於213的字典序，所以213的康託展開值是2，序號為3。

排列排列康託展開值123
1
0*2!+0*1!+0*0!
132
2
0*2!+1*1!+0*0!213
31*2!+0*1!+0*0!231
4
1*2!+1*1!+0*0!31252*2!+0*1!+0*0!321
62*2!+1*1!+0*0!
計算公式

 其中，ai 為第 i 位後的 i-1 位比第 i 位小的個數（i 為從右往左）。

舉例說明

已知Set={1,2,3,4,5}, 求n==34152在Set全排列從小到大排序後在第幾位。

在34152 中，不論從左向右還是從右向左開始建立（不是 i 的順序，i 都是從右向左），我們都可以得到以下這張表。

從左向右為例解釋：

n5=3，在後面4位中，有1 和2小於n5，於是a5=2

n4=4，在後面3位中，有1和2小於n4，於是a4=2

n3=1，在後面2位中，沒有數小於n3，於是a3=0

n2=5，在後面1位中，有2小於n2，於是a2=1

n1=2，在後面0位中，沒有數小於n1，於是a1=0

根據公式可得：

所以34152前面的排列共有61個，結果就是61+1=62。

C/C++語言實現代碼

#include <bits/stdc++.h>using namespace std;
int cantor(int n){    const int factorial[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};     stringstream ss;    ss << n;    string s = ss.str();    int num = s.length(), x = 0, temp;    for (int i = 0; i < num; i++)    {        temp = 0;        for (int j = i + 1; j < num; j++)            if (s[i] > s[j])                temp++;        x += temp * factorial[num - i - 1];    }    return x + 1;}
int main(int argc, char *argv[]){    int n;
    cin >> n;    cout << cantor(n) << endl;
    return 0;}
逆康託展開
  逆康託展開只需要將康託展開的過程反過來即可，將序號減一後，依次對階乘作商取餘。代碼如下：
#include <bits/stdc++.h>using namespace std;
int decantor(int n, vector<int> v){    const int factorial[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};     int num = v.size();    stringstream ss;    n--;    for (int i = 0; i < num; i++)    {        int temp = n / factorial[num - i - 1];        n %= factorial[num - 1 - i];        ss << v[temp];        v.erase(v.begin() + temp);    }    return atoi(ss.str().c_str());}
int main(int argc, char *argv[]){    int n, temp;    vector<int> vec;    vec.clear();
    cout << "input index: ";    cin >> n;    cout << "input set, end with -1:" << endl;    while (cin >> temp, temp != -1)        vec.push_back(temp);    sort(vec.begin(), vec.end());
    cout << decantor(n, vec) << endl;    return 0;}
如有錯誤還請指出。