Cantor expansion（康托展開）

定義：

          将一個整數X展開為如下形式：

           X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0! （其中，a為整數，并且0<=a[i]<i(1<=i<=n)）

全排列的編碼：

          {1,2,3,4,...,n}的排列總共有n!種，将它們從小到大排序，怎樣知道其中一種排列是有序序列中的第幾個？ 如 {1,2,3,4,5,6,7,8,9} 按從小到大排列一共9!個。想知道357412968是全排列第幾個大的數。

答案是：98884。因為X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884。

解釋：排列的第一位是3，比3小的數有兩個，是以最高位（第一位）可以是1或者2，而後面有8位，不管是它們什麼，反正有8！種排列。（2*8！）

           排列的第二位是5，比5小的數有四個，但是3之前出現過，是以第二位可以使1,2或者4，而後面有7位，有7！種排列。（3*7！）

           以此類推。。。。。。

全排列的解碼：

         既然康托展開是一個雙射，那麼一定可以通過康托展開值求出原排列，即可以求出n的排列中第x小的排列。

如何找出第16個（按字典序的）{1,2,3,4,5}的全排列？

答案是：1,4,3,5,2。

           解釋：

                1. 首先用16-1得到15                 2. 用15去除4! 得到0餘15                 3. 用15去除3! 得到2餘3                 4. 用3去除2! 得到1餘1                 5. 用1去除1! 得到1餘0                    有0個數比它小的數是1，是以第一位是1                  有2個數比它小的數是3，但1已經在之前出現過了是以是4                  有1個數比它小的數是2，但1已經在之前出現過了是以是3                  有1個數比它小的數是2，但1,3,4都出現過了是以是5                 最後一個數隻能是2                   是以排列為1,4,3,5,2

題目：http://acm.nyist.net/JudgeOnline/problem.php?pid=139

      http://acm.nyist.net/JudgeOnline/problem.php?pid=143

          http://acm.hdu.edu.cn/showproblem.php?pid=1430