## 一.题目描述  题目的意思是，假设有{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)