康托展開

可以理解為把一個全排列映射到一個數(shù)上面，因為全排列如果按照從小到大或者從大到小，肯定是有一個確定的序列的。

一般是從小到大的序列個數(shù)。我們就是要求出這個序列的位置。，想法很簡答，就是求出前面比他小的個數(shù)就可以了。

理解為一個每位都是階乘進位的數(shù)轉(zhuǎn)化為10進制的數(shù)。思路如下：
先準(zhǔn)備求每一位的階乘，然后從高位開始統(tǒng)計后面有多少個數(shù)比他小記錄這個個位數(shù)，然后乘以后面?zhèn)€數(shù)的階乘，再把它累加起來。

x[i]表示第i位后面比他小的個數(shù),那么

$$\sum _1^{N}x[i]?Fac[N?i]$$
這樣就能求出比他小的有多少個了，也能求出他是第幾個序列。

//求出階乘 void init(){Fac[0] = 1;for(int i=1;i<=N;++i){Fac[i] = Fac[i-1]*i;} }int kangtuo(int n,char a[]) {int i,j,t,sum;sum=0;for( i=0; i<n ;++i){t=0;for(j=i+1;j<n;++j)if( a[i]>a[j] )++t;sum+=t*fac[n-i-1];}return sum+1; }

逆康托展開

相當(dāng)于知道序列位置求這個位置的數(shù)。
想法也很簡單，因為對于每位的Fac[N-i]都比后面說有的和都大，所以用pos/Fac[N-1]求得的就是x[i],同理pos%Fac[N-i]就是后面的和。

我們維護一個序列st始終按照從小到大排列，那么已知某位置的x[i]，那么這個位置的數(shù)就是st[x[i]+1]。

void init(){Fac[0] = 1;for(int i=1;i<=N;++i){Fac[i] = Fac[i-1]*i;} } void reverse_kangtuo(int n,int k,char s[]) {int i, j, t, vst[8]={0};--k;for (i=0; i<n; i++){t = k/fac[n-i-1];for (j=1; j<=n; j++)if (!vst[j]){if (t == 0) break;--t;}s[i] = '0'+j;vst[j] = 1;k %= fac[n-i-1];} }

總結(jié)

以上是生活随笔為你收集整理的数学--数论--康托展开与逆康托展开的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。