Permutation Sequence
最后更新于：2022-04-02 01:12:22
# 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 factorial = vector(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 nums;
for (int i = 1; i < n + 1; ++i) {
nums.push_back(i);
}
vector 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 to a string
std::stringstream result;
std::copy(perm.begin(), perm.end(), std::ostream_iterator(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 nums = new ArrayList();
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)
';