LeetCode:Permutation Sequence

LeetCode:Permutation Sequence2015-02-15题目链接：http://oj.leetcode.com/problems/permutation-sequence/

The set [1,2,3,…,n] contains a total of n！ unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence （ie, for n = 3）:

"123"

"132"

"213"

"231"

"312"

"321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

在面试时需要注意咨询面试官，输入的k 是否小于1 或者是否大于n！

分析：按照一般的递归求全排列的算法（LeetCode:Permutations），输出的序列不是按字典序有序的，比如对于1,2,3，输出序列为：

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2

以3开头的排列举例，算法中是把1和3交换得到3 2 1，然后递归的求解，但是3 2 1不是以3开头的最小序列，应该是3 1 2. 为了得到有序的序列，我们不是把1 3 交换，而是应该把3移动到1的前面，这样得到的第一个以3开头的序列就是3 1 2。因此有如下的算法：

算法1

class Solution {private:int k_;string res_;public:string getPermutation（int n, int k） {k_ = k;string str = string（"123456789"）.substr（0, n）;int cnt = 0;PermutationRecur（str, 0, cnt）;return res_;}bool PermutationRecur（string &str, int index, int &cnt）{int len = str.size（）;if（index == len - 1）{cnt++;if（cnt == k_）{res_ = str;return true;}}else{for（int i = index; i < len; i++）{rotate（&str[index], &str[i], &str[i+1]）;if（PermutationRecur（str, index + 1, cnt））return true;rotate（&str[index], &str[i], &str[i+1]）;}}return false;}};

该算法在大数据下超时了。

算法2

利用next_permutation函数（该函数的详解请参考LeetCode:Permutations算法3），这种做法也超时了

class Solution {public:string getPermutation（int n, int k） {string str = string（"123456789"）.substr（0, n）;for（int i = 1; i <= k-1; i++）next_permutation（str.begin（）, str.end（））;return str;}};

算法3

上面的算法都是逐个的求排列，有没有什么方法不是逐个求，而是直接构造出第k个排列呢？我们以n = 4，k = 17为例，数组src = [1,2,3,...,n]。

第17个排列的第一个数是什么呢：我们知道以某个数固定开头的排列个数 = （n-1）！ = 3！ = 6, 即以1和2开头的排列总共6*2 = 12个，12 < 17, 因此第17个排列的第一个数不可能是1或者2，6*3 > 17, 因此第17个排列的第一个数是3。即第17个排列的第一个数是原数组（原数组递增有序）的第m = upper（17/6） = 3（upper表示向上取整）个数。

第一个数固定后，我们从src数组中删除该数，那么就相当于在当前src的基础上求第k - （m-1）*（n-1）！ = 17 - 2*6 = 5个排列，因此可以递归的求解该问题。

class Solution {public:string getPermutation（int n, int k） {string str = string（"123456789"）.substr（0, n）;string res（n, " "）;for（int i = 0; i < n; i++）res[i] = helper（str, k）;return res;}//以s中字符构造的全排列中，返回第k个排列的第一个字符，并且删除s中该字符//s中字符递增有序char helper（string &s, int &k）{int tmp = factorial（s.size（）-1）, i = （k-1）/tmp;char res = s[i];s.erase（i, 1）;k -= i*tmp;//更新kreturn res;}//求正整数n的阶乘int factorial（int n）{int res = 1;for（int i = 2; i <= n; i++）res *= i;return res;}};

当然也可以非递归实现

class Solution {public:string getPermutation（int n, int k） {int total = factorial（n）;string candidate = string（"123456789"）.substr（0, n）;string res（n," "）;for（int i = 0; i < n; i++）//依次计算排列的每个位{total /= （n-i）;int index = （k-1） / total;res[i] = candidate[index];candidate.erase（index, 1）;k -= index*total;}return res;}int factorial（int n）{int res = 1;for（int i = 2; i <= n; i++）res *= i;return res;}};

From：cnblogs tenos