定義：

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

原理：

• 代表在位置i后面且小于的值得個數
• (n-k)!代表階乘

康托展開代碼：

const int fact[10]={1,1,2,6,24,120,720,5040,40320,362880};int cantor(int a[],int n) {int ans=0;for(int i=1;i<=n;i++){int cnt=0;for(int j=i+1;j<=n;j++)if(a[j]<a[i])cnt++;ans+=cnt*fact[n-i];}return ans; }

康托逆展開：

我們以[4,2,5,1,3]為例，計算出來的康托值為82,我們該怎么用37回到序列[4,2,5,1,3]呢？

82/(4!)，商為3，余數為10：商為3說明在第一位后面有3個比當前位置小的數，那么我們在這一位填充第4大的數，即4

10/(3!)，商為1，余數為4：商為1說明在第二位后面有1個比當前位置小的數，那么我們在這一位填充除了4以外(4已經用過了)，第2大的數，即2

4/(2!)，商為2，余數為0：商為2說明在第三位后面有2個比當前位置大的數，那么我們在這一位填充剩余三個數中第三大的數，即5

0/(1!)，商為0，余數為0：商為0說明在第四位后面沒有比當前位置大的數，那么我們在這一位填充剩余數中最小的數，即1

最后將未填充的數(3)填到最后一位即可

康托逆展開代碼：

const int fact[10]={1,1,2,6,24,120,720,5040,40320,362880};vector<int> decontor(int x,int n) {vector<int>ans;vector<int>num;for(int i=1;i<=n;i++)num.push_back(i);for(int i=n;i>=1;i--){int pos=x/fact[i-1];x%=fact[i-1];ans.push_back(num[pos]);num.erase(num.begin()+pos);}return ans; }

?

?

總結

以上是生活随笔為你收集整理的康托展开与逆展开(原理+模板)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。