问题：
对于给定序列1...n，permutations共同拥有 n！个，那么随意给定k，返回第k个permutation。0 < n < 10。
分析：
这个问题要是从最小開始直接到k，预计会超时，受10进制转换为二进制的启示，对于排列，比方 1,2,3 是第一个，那么3！= 6，所以第6个就是3,2,1。也就是说，从開始的最小的序列開始，到最大的序列，就是序列个数的阶乘数。那么在1，3 , 2的时候呢？调整一下，变成2,1,3，就能够继续。
实现：
int getFactorial(int n)
{
int factorial[10] = {-1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
return factorial[n];
}
int checkFactorial(int n){
// n is small, use liner search.
int factorial[10] = {-1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
for (int i = 1; i < 10; ++i)
{
if(n >= factorial[i] && n < factorial[i + 1])
return i;
}
return 0;
}
void nextPermutetion(string &num)
{
int i = num.size() - 1;
while (i >= 1)
{
if(num[i] > num[i - 1])
{
--i;
int ii = num.size() - 1;
while (ii > i && num[ii] <= num[i]) --ii;
if(ii > i)
{
swap(num[i], num[ii]);
reverse(num.begin() + i + 1, num.end());
break;
}
}
else
--i;
}
}
string getPermutation(int n, int k) {
if(k > getFactorial(n))
return "";
if(k <= 0 || 0 > n || n >= 10)
return "";
//init the permutation.
string permu(n,'0');
for(int i = 0; i < n; ++i)
permu[i] = i + 1 + '0';
if(k == 1)
return permu;
while (k > 0)
{
int fac = checkFactorial(k);
//adjust
if(permu[n - 1] <= permu[n - fac])
{
nextPermutetion(permu);
}
reverse(permu.begin() + (n - fac), permu.end());
k -= getFactorial(fac);
}
return permu;
}
说明：实现有些复杂，http://blog.csdn.net/doc_sgl/article/details/12840715 这里有个简单的纯数学解法。
转载于:https://www.cnblogs.com/bhlsheji/p/3780036.html
相关资源：数据结构—成绩单生成器
