康拓展開和逆展開

什麼是康托展開？

           康托展開其實就是一個解決問題的數學公式，因為這個公式是德國的數學家康托爾發明的，是以以他的名字命名為康托展開。

主要表現形式是什麼呢？

            給定一個整數X，根據康托展開的公式，我們可以把這個X展開為：X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!   

其中，a為整數，并且0<=a[i]<i(1<=i<=n)（百度百科），其中的a[n]和n各自代表什麼意思呢？  舉個例子：對于一個數 5698452 ，它是一個7位數，是以此時 n = 7，對于此數字中每個數字是第幾位的問題，跟我們平時習慣的從地位向高位查是一樣的，即5是第7位，2是第一位，接下來a[n]是不是就代表第n位上的那個數字呢？ 答案是：NO ，拿最高位的5來說，我們找找它前面的幾位中有幾個比它小，很容易找到有兩個： 4 和 2，是以a[7]=2,，即a[n]代表的是比在n這一位上的數字小的數的個數，接下來，比6小的數有4，5，2三個，是以a[6]=3，接着，a[5] = 4 ,a[4] = 3 ,a[3] = 1 , a[2]=1 , a[1] = 0, 是以

X = 2*6！+3*5！+4*4！+3*3！+1*2！+0*0！ 那 X 代表什麼意義呢？  

總結：n表示這個數字的位數（或者包含幾個數字）；a[n]代表的是比在n這一位上的數字小的數的個數；

        接下來我們再看X代表的意義，說到X就必須說到康托展開究竟有什麼用，究竟在哪裡能用到，應該怎麼用的問題。

康托展開所要解決的問題就是關于序列的問題：給定一個序列，如：123，它有六種排列方式 123 ，132 ，213 ，231， 312 ，321 我們把這六個數按從小到大的順序進行排列 ，然後給其中的一個數，求此數前面還有幾個數（也就是有幾個數比此數小），我們就可以用康托展開來求，而且給一個數，可以求排名此數位的序列式什麼（康托逆展開）。

總結：主要用處就是根據序列求排名，根據排名求序列。

c語言 由序列求排名的代碼：

#include<stdio.h>
int p[]={1,1,2,6,24,120,720,5040,40320,362880};
int kangtuo(int *s,int n)
{
	int count=0,sum=0,i,j;
	for(i=0;i<n;i++)
	{
		count=0;
		for(j=i+1;j<n;j++)
		{
			if(s[i]>s[j])
			count++;
		}
		
		sum=sum+count*p[n-i-1];
	}
	return sum;
}
int main(void)
{	
	int n=3,result;
	int s[3]={2,1,3};
	 result = kangtuo(s,n);
	 printf("%d\n",result);
	 return 0;<span style="font-family: arial, 宋體, sans-serif;">	</span>
           

<span style="font-family: arial, 宋體, sans-serif;">} </span>
           

最後輸出結果為 2 ，是以在 213 前面有兩個數，是以213排在第三位。

康托的逆展開

所謂康托的逆展開就是知道排名求序列

用一個例子解釋其中的原理：

（本例來自百度百科） 例： {1,2,3,4,5}的 全排列，并且已經從小到大排序完畢 (1)找出第96個數 首先用96-1得到95 用95去除4! 得到3餘23 有3個數比它小的數是4 是以第一位是4 用23去除3! 得到3餘5 有3個數比它小的數是4但4已經在之前出現過了是以第二位是5（4在之前出現過，是以實際比5小的數是3個） 用5去除2!得到2餘1 有2個數比它小的數是3，第三位是3 用1去除1!得到1餘0 有1個數比它小的數是2，第二位是2 最後一個數隻能是1 是以這個數是45321

#include <iostream>
using namespace std;

void CantorReverse(int index,int *p,int n);  //康托展開逆用，判斷給定的位置中的排列
long int fac[]={1,1,2,6,24,120,720,5040,40320,362880}; //表示階乘運算的結果
//long int fac[]={0!,1!,2!,3!,4!,5!,6!,7!,8!,9!};

int main(int argc,char *argv)
{
    int len=5; 
    int *s=(int *)malloc(len*sizeof(int));
    CantorReverse(96,s,len);  //有數字{12345}組成的所有排列中，求出第96個排列的順序
    for(int i=0;i<len;i++)
        cout<<s[i];
    cout<<endl;
    free(s);
    return 0;
}
void CantorReverse(int index,int *p,int n)
{
    index--;     //勿丢
    int i,j;
    bool hash[10]={0};
    for(i=0;i<n;i++)
    {
        int tmp=index/fac[n-1-i];  //tmp表示有tmp個數字比目前位置上的數字小
        for(j=0;j<=tmp;j++)
            if(hash[j]) tmp++;
        p[i]=tmp+1;
        hash[tmp]=1; 
        index%=fac[n-1-i];
    }
    return;
}
           

（此代碼轉載自部落格園 http://www.cnblogs.com/dong008259/archive/2011/12/12/2283436.html）

（如有問題，敬請指出，共同學習，不勝感激）！