# Permutation Sequence ### Source - leetcode: [Permutation Sequence | LeetCode OJ](https://leetcode.com/problems/permutation-sequence/) - lintcode: [(388) Permutation Sequence](http://www.lintcode.com/en/problem/permutation-sequence/) ### Problem Given *n* and *k*, return the *k*-th permutation sequence. #### Example For `n = 3`, all permutations are listed as follows: ~~~ "123" "132" "213" "231" "312" "321" ~~~ If `k = 4`, the fourth permutation is `"231"` #### Note *n* will be between 1 and 9 inclusive. #### Challenge O(n*k) in time complexity is easy, can you do it in O(n^2) or less? ### 題解 和題 [Permutation Index](http://algorithm.yuanbin.me/zh-cn/exhaustive_search/permutation_index.html) 正好相反，這里給定第幾個排列的相對排名，輸出排列值。和不同進制之間的轉化類似，這里的『進制』為`1!, 2!...`, 以n=3, k=4為例，我們從高位到低位轉化，直覺應該是用 `k/(n-1)!`, 但以 n=3,k=5 和 n=3,k=6 代入計算后發現邊界處理起來不太方便，故我們可以嘗試將 k 減1進行運算，后面的基準也隨之變化。第一個數可以通過`(k-1)/(n-1)!`進行計算，那么第二個數呢？聯想不同進制數之間的轉化，我們可以通過求模運算求得下一個數的`k-1`, 那么下一個數可通過`(k2 - 1)/(n-2)!`求得，這里不理解的可以通過進制轉換類比進行理解。和減掉相應的階乘值是等價的。 ### Python ~~~ class Solution: """ @param n: n @param k: the k-th permutation @return: a string, the k-th permutation """ def getPermutation(self, n, k): # generate factorial list factorial = [1] for i in xrange(1, n + 1): factorial.append(factorial[-1] * i) nums = range(1, n + 1) perm = [] for i in xrange(n): rank = (k - 1) / factorial[n - i - 1] k = (k - 1) % factorial[n - i - 1] + 1 # append and remove nums[rank] perm.append(nums[rank]) nums.remove(nums[rank]) # combine digits return "".join([str(digit) for digit in perm]) ~~~ ### C++ ~~~ class Solution { public: /** * @param n: n * @param k: the kth permutation * @return: return the k-th permutation */ string getPermutation(int n, int k) { // generate factorial list vector<int> factorial = vector<int>(n + 1, 1); for (int i = 1; i < n + 1; ++i) { factorial[i] = factorial[i - 1] * i; } // generate digits ranging from 1 to n vector<int> nums; for (int i = 1; i < n + 1; ++i) { nums.push_back(i); } vector<int> perm; for (int i = 0; i < n; ++i) { int rank = (k - 1) / factorial[n - i - 1]; k = (k - 1) % factorial[n - i - 1] + 1; // append and remove nums[rank] perm.push_back(nums[rank]); nums.erase(std::remove(nums.begin(), nums.end(), nums[rank]), nums.end()); } // transform a vector<int> to a string std::stringstream result; std::copy(perm.begin(), perm.end(), std::ostream_iterator<int>(result, "")); return result.str(); } }; ~~~ ### Java ~~~ class Solution { /** * @param n: n * @param k: the kth permutation * @return: return the k-th permutation */ public String getPermutation(int n, int k) { // get factorial array int[] fact = new int[n]; fact[0] = 1; for (int i = 1; i < n; i++) { fact[i] = fact[i - 1] * i; } // generate nums 1 to n List<Integer> nums = new ArrayList<Integer>(); for (int i = 1; i <= n; i++) { nums.add(i); } // get the permutation digit StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { // k begins from 1, so (1, 2) is a group int rank = (k - 1) / fact[n - i - 1]; k = (k - 1) % fact[n - i - 1] + 1; // ajust the mapping of rank to num sb.append(nums.get(rank)); nums.remove(nums.get(rank)); } return sb.toString(); } } ~~~ ### 源碼分析 源碼結構分為三步走， 1. 建階乘數組 1. 生成排列數字數組 1. 從高位到低位計算排列數值 ### 復雜度分析 幾個 for 循環，時間復雜度為 O(n)O(n)O(n), 用了與 n 等長的一些數組，空間復雜度為 O(n)O(n)O(n). ### Reference - [Permutation Sequence 解題報告](http://blog.sina.com.cn/s/blog_eb52001d0102v1ss.html) - [Permutation Sequence 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/permutation-sequence/) - [c++ - How to transform a vector into a string? - Stack Overflow](http://stackoverflow.com/questions/2518979/how-to-transform-a-vectorint-into-a-string)