康托展開在全排列中使用（C++實作）

1. 在一個全排列中，比如在1,2,3,4,5所有的全排列中，如何确定34152在1,2,3,4,5所欲排列中排第幾？
2. 康托展開的公式為以1,2,3,4,5為例，那麼康托展開的公式為
3. X=a[5](5-1)!+a[4](4-1)!+a[3](3-1)!+a[2](2-1)!+a[1]*(1-1)
4. 其中1<=a[i]<=5，a[i]表示（從首位開始算）指的是位于位置i後面的數小于a[i]值的個數。比如34152的康托展開式子為：

5. 首位3在所有未出現的數字中排第3（1,2）

   是以a[5]=2（小于3的有2個）

   第二位4在所有未出現的數字中排第三（1,2）

   是以a[4]=2（小于4的有2個）

   同理a[3]=0 a[2]=1 a[2]=0

   X=a[5](5-1)!+a[4](4-1)!+a[3](3-1)!+a[2](2-1)!+a[1](1-1)!

   X=24!+23!+02！+11！+00！

   X=61

   那麼在34152小的全排列有61個，那麼34152排在全排列的第62個。康托展開就是上述的描述。當然還有康托展開的逆運算。也是很有用的。C++代碼實作如下所示：

   #include

   using namespace std;

   int getSmaller(int intarr, int key)//計算位置比key小的，标志位為1（說明沒有參與康拓計算過的數字）的個數。

   {

   int sum = 0;

   for (int i = 1; i < key; i++)

   {

   if (intarr[i] == 1)

   {

   sum++;

   }

   }

   return sum;

   }

   int jiecheng(int n)//計算N的階乘

   {

   if (n == 1 || n == 0)

   {

   return 1;

   }

   else

   {

   return njiecheng(n - 1);

   }

   }

   int getCantor(int number, int length)

   {

   int len = length + 1;

   int *numflag = new int[len];//定義标志為函數，标志i位是否已經參與過康拓計算。1為沒參與過

   for (int i = 1; i < len; i++)

   {

   numflag[i] = 1;

   }

   int numarr = new int[len];

   int temp = number;

   for (int i = 1; i < len; i++)//把所有數字通過求餘運算放到一個數組裡面，便于後序康拓展開運算。

   {

   numarr[i] = temp%10;

   int ai = temp % 10;

   temp = temp / 10;

   }

   int cantornum = 0;

   for (int i = len - 1; i >= 1; i–)

   {

   int key = numarr[i];

   int ai = getSmaller(numflag, key);//擷取位置比key小的，個數。

   numflag[key] = 0;//當改為參與過康拓展開計算時，标志位設為1；

   int aikey = jiecheng(i - 1);

   cantornum += aiaikey;//計算康托展開

   }

   return cantornum+1;

   }

   int main()

   {

   cout << getCantor(34152,5) << endl;

   system(“pause”);

   return 0;

   }

   康托展開在全排列的計算中有重要的作用，比如字元串全排列的的字典序的排序等等運算。通過康托展開我們可以迅速确認一個全排順序的位置，年與後續的計算和處理