一.题目描述

题目的意思是，假设有{1,2,3,4,…,n}，对其中的元素进行排列，总共有n!种组合，将它们从小到大排序，问其中第k个组合的形式是怎样的？<喎"http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+tv4uzOLEv7fWzvY8L3N0cm9uZz48L3A+DQo8cD48c3Ryb25nPre9t6jSuzwvc3Ryb25nPqO6v8nS1NK7uPbSu7j2tcSwtLTO0PKxqcGmx/O94qGjvt/M5cq1z9a/ybLO1dXM4sS/o7pOZXh0IFBlcm11dGF0aW9uoaPV4sDvsqLDu9PQyrXP1qOs1vfSqtHQvr+1xMrHt723qLb+tcRDYW50b3IgZXhwYW5zaW9uy+O3qKGjPC9wPg0KPHA+PHN0cm9uZz63vbeotv48L3N0cm9uZz6jusr90ae94reoo7pDYW50b3IgZXhwYW5zaW9uPC9wPg0KPHA+Q2FudG9yIGV4cGFuc2lvbsvjt6i1xMu8z+vKx6Os1No8Y29kZT5uITwvY29kZT649sXFwdDW0KOstdrSu867tcTUqsvY19zKxzxjb2RlPihuLTEpITwvY29kZT7Su9fps/bP1rXEo6zSsr7Ny7XI57n7PGNvZGU+cCA9IGsgLyAobi0xKSE8L2NvZGU+o6zEx8O0xcXB0LXE1+6/qsq80ru49tSqy9jSu7aoysc8Y29kZT5udW1zW3BdPC9jb2RlPqGj0tTPwrmryr24+LP2wcvIq8XFwdC1vdK7uPbX1Mi7yv21xNK70rvLq8nko7o8L3A+DQo8cHJlIGNsYXNzPQ=="brush:java;">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.hint 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的取值超过可能的组合数量时：