# Question

Formatted question description: https://leetcode.ca/all/60.html

60. 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.

@tag-backtracking
@tag-math



# Algorithm

### Math

Assuming there are n elements, the K-th permutation result string is

a1, a2, a3, ..... ..., an


So which number is a1?

So here, we remove a1, then the remaining permutation is

a2, a3, .... .... an


, a total of n-1 elements. There are n-1 elements in total (n-1)! group arrangement, then you can know

Set variable K1 = K, a1 = K1 / (n-1)!

Similarly, the value of a2 can be derived as

a2 = K2 / (n-2)!
K2 = K1 % (n-1)!
.......
a(n-1) = K(n-1) / 1!
K(n-1) = K(n-2) / 2!

an = K(n-1)


### Cantor Expand

How to find the 16th (lexicographically) {1,2,3,4,5} permutation?

1. First use 16-1 to get 15 — @note:@memorize: “-1” is key to understand, k-th permutation meaning k-1, (i.e. code line below k = k - 1; // k 变为 k - 1)
• @note@note: eg: first permutation, k=1, after divided by 4!, 3!, 2!, 1!, should be 0,0,0,0,
• but 1/1! will gerate 1, which is wrong!
• so should be 0/1! = 0
2. Divide 4 by 15! Get 0 remaining 15

3. Divide 3 with 15! Get 2 remaining 3

4. Divide 2 with 3! Get 1 remaining 1

5. Divide 1 by 1! Get 1 more than 0

There are 0 numbers smaller than it is 1, so the first digit is 1.

There are 2 numbers that are smaller than it is 3, but 1 has appeared before, so it is 4.

There is 1 number smaller than it is 2, but 1 has appeared before, so it is 3.

There is 1 number smaller than it is 2, but 1, 3, and 4 have all appeared, so it is 5.

The last number can only be 2

So the arrangement is 1 4 3 5 2

# Code

• import java.util.ArrayList;
import java.util.List;

public class Permutation_Sequence {

public static void main(String[] args) {
Permutation_Sequence out = new Permutation_Sequence();
Solution s = out.new Solution();

System.out.println(s.getPermutation(4, 17)); // 3412
}

// time: O(N)
// space: O(N)
public class Solution {
public String getPermutation(int n, int k) {

List<Integer> nums = new ArrayList<Integer>();
List<Integer> factorial = new ArrayList<Integer>(); // total n elements
for (int i = 1; i <= n; i++) {

// size=n+1, will be [1,1,2,6,24]
// so that, factorial(k) is k!
}

StringBuilder result = new StringBuilder();
k = k - 1; // k 变为 k - 1
for (int i = n; i > 0; i--) {

int digit = k / factorial.get(i - 1);
result.append(nums.get(digit));

k %= factorial.get(i - 1);
nums.remove(digit); // remove by object
}
return result.toString();
}
}

}

############

class Solution {
public String getPermutation(int n, int k) {
StringBuilder ans = new StringBuilder();
boolean[] vis = new boolean[n + 1];
for (int i = 0; i < n; ++i) {
int fact = 1;
for (int j = 1; j < n - i; ++j) {
fact *= j;
}
for (int j = 1; j <= n; ++j) {
if (!vis[j]) {
if (k > fact) {
k -= fact;
} else {
ans.append(j);
vis[j] = true;
break;
}
}
}
}
return ans.toString();
}
}

• // OJ: https://leetcode.com/problems/permutation-sequence/
// Time: O(NK)
// Space: O(1)
class Solution {
public:
string getPermutation(int n, int k) {
string ans;
for (int i = 0; i < n; ++i) ans += ('1' + i);
while (--k) next_permutation(begin(ans), end(ans));
return ans;
}
};

• class Solution:
def getPermutation(self, n: int, k: int) -> str:
nums = list(range(1, n + 1))
factorial = [1] * (n + 1)
for i in range(1, n + 1):
factorial[i] = factorial[i - 1] * i

result = []
k -= 1
for i in range(n, 0, -1):
digit = k // factorial[i - 1]
result.append(str(nums[digit]))
k %= factorial[i - 1]
nums.pop(digit)

return ''.join(result)

##########

class Solution:
def getPermutation(self, n: int, k: int) -> str:
ans = []
vis = [False] * (n + 1)
for i in range(n):
fact = 1
for j in range(1, n - i):
fact *= j
for j in range(1, n + 1):
if not vis[j]:
if k > fact:
k -= fact
else:
ans.append(str(j))
vis[j] = True
break
return ''.join(ans)

############

class Solution(object):
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
visited = [0 for i in range(n)]
fact = [math.factorial(n - i - 1) for i in range(n)]
ans = ""
k -= 1
for i in range(n):
t = k / fact[i]
for j in range(n):
if not visited[j]:
if t == 0:
break
t -= 1
ans += str(j + 1)
k %= fact[i]
visited[j] = 1
return ans


• func getPermutation(n int, k int) string {
ans := make([]byte, n)
vis := make([]bool, n+1)
for i := 0; i < n; i++ {
fact := 1
for j := 1; j < n-i; j++ {
fact *= j
}
for j := 1; j <= n; j++ {
if !vis[j] {
if k > fact {
k -= fact
} else {
ans[i] = byte('0' + j)
vis[j] = true
break
}
}
}
}
return string(ans)
}

• public class Solution {
public string GetPermutation(int n, int k) {
var ans = new StringBuilder();
int vis = 0;
for (int i = 0; i < n; ++i) {
int fact = 1;
for (int j = 1; j < n - i; ++j) {
fact *= j;
}
for (int j = 1; j <= n; ++j) {
if (((vis >> j) & 1) == 0) {
if (k > fact) {
k -= fact;
} else {
ans.Append(j);
vis |= 1 << j;
break;
}
}
}
}
return ans.ToString();
}
}