Permutation Sequence
最后更新于：2022-04-01 22:55:24
## 一.题目描述
题目的意思是，假设有{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
#include
#include
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)
';