## 一.題目描述  題目的意思是，假設有{1,2,3,4,…,n}，對其中的元素進行排列，總共有n!種組合，將它們從小到大排序，問其中第k個組合的形式是怎樣的？ ## 二.題目分析 **方法一**：可以一個一個的按次序暴力求解。具體實現可參照題目：Next Permutation。這里并沒有實現，主要研究的是方法二的Cantor expansion算法。 **方法二**：數學解法：Cantor expansion Cantor expansion算法的思想是，在`n!`個排列中，第一位的元素總是`(n-1)!`一組出現的，也就說如果`p = k / (n-1)!`，那么排列的最開始一個元素一定是`nums[p]`。以下公式給出了全排列到一個自然數的一一雙射： ~~~ X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0! ~~~ 舉個例子： 問`1324`是`{1,2,3,4}`排列數中第幾個組合： 第一位是`1`，小于`1`的數沒有，是`0`個，`0*3!`，第二位是`3`，小于`3`的數有`1`和`2`，但`1`已經存在于第一位了，所以只有一個數`2`，`1*2!`?。第三位是`2`小于`2`的數是`1`，但`1`在第一位，所以有`0`個數，`0*1!`，所以比`1324`小的排列有`0*3!+1*2!+0*1!=2`個，`1324`是第`3`個組合。 以上是Cantor編碼的過程，即**把一個全排列映射1324為一個自然數3**，而該題目是已知一個自然數`k`，求其對應的全排列，相對以上步驟來說是一個解碼的過程，下面給出一個具體的例子： 如何找出`{1,2,3,4,5}`的第`16`個排列？? 1\. 首先用`16-1`，得到`15`；? 2\. 用`15`去除`4!`?，得到`0`，余`15`；? 3\. 用`15`去除`3!`?，得到`2`，余`3`；? 4\. 用`3`去除`2!`?，得到`1`，余`1`；? 5\. 用`1`去除1! ，得到`1`，余`0`；? 6\. 有`0`個數比它小的數是`1`，所以第一位是`1`；? 7\. 有`2`個數比它小的數是`3`，但`1`已經在之前出現過，所以第二位是`4`；? 8\. 有`1`個數比它小的數是`2`，但`1`已經在之前出現過了所以第三位是`3`；? 9\. 有`1`個數比它小的數是`2`，但1,3,4都出現過了所以第四位是`5`；? 10\. 根據上述推論，最后一個數只能是`2`； 所以排列為`{1,4,3,5,2}`。 按照以上思路，可以開始設計算法。 ## 三.示例代碼 ~~~ #include <iostream> #include <string> #include <iterator> using namespace std; class Solution { public: string PermutationSequence(int n, int k) { int total = CombinedNumber(n - 1); if (k > total) { cout << "The k is larger then the total number of permutation sequence:" << total << endl; return "Null!"; } string a(n, '0'); for (int i = 0; i < n; ++i) a[i] += i + 1; // sorted // Cantor expansion string s = a, result; k--; // (k - 1) values are less than the target value for (int i = n - 1; i > 0; --i) { auto ptr = next(s.begin(), k / total); result.push_back(*ptr); s.erase(ptr); // delete the already used number k %= total; // update the dividend total /= i; // update the divider } result.push_back(s[0]); // The last bit return result; } private: int CombinedNumber(int n) { int num = 1; for (int i = 1; i < n + 1; ++i) num *= i; return num; } }; ~~~ 以下是簡易的測試代碼： ~~~ #include "PermutationSequence.h" int main() { Solution s; int n = 6, k = 150; string result = s.PermutationSequence(n, k); std::cout << "n = " << n << " and the " << k << "th sequence is: " << result << std::endl; getchar(); return 0; } ~~~ 一個正確的測試結果，`n = 6`，?`k = 16`：  當`k`的取值超過可能的組合數量時：  ## 四.總結 該題應嘗試使用Cantor expansion解法來做，數學的魅力是無窮的。 參考資料：[http://www.bianceng.cn/Programming/sjjg/201407/43080.htm](http://www.bianceng.cn/Programming/sjjg/201407/43080.htm)