# Permutation Sequence

## Question

### Problem Statement

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?

## 题解

### 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) {
if (n <= 0 && k <= 0) return "";

int fact = 1;
// generate nums 1 to n
List<Integer> nums = new ArrayList<Integer>();
for (int i = 1; i <= n; i++) {
fact *= i;
}

// get the permutation digit
StringBuilder sb = new StringBuilder();
for (int i = n; i >= 1; i--) {
fact /= i;
// take care of rank and k
int rank = (k - 1) / fact;
k = (k - 1) % fact + 1;
// ajust the mapping of rank to num
sb.append(nums.get(rank));
nums.remove(rank);
}

return sb.toString();
}
}


### 源码分析

1. 建阶乘数组
2. 生成排列数字数组
3. 从高位到低位计算排列数值