source: https://leetcode.com/problems/permutation-sequence/
C/C++ Solution to LeetCode problem 60. Permutation Sequence.
Problem
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 for n = 3
:
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Examples
Example 1:
Input: n = 3, k = 3
Output: “213”
Example 2:
Input: n = 4, k = 9
Output: “2314”
Example 3:
Input: n = 3, k = 1
Output: “123”
Constraints
1 <= n <= 9
1 <= k <= n!
Solution
We can generate k!
permutations, but this is not an optimal solution, so:
- Let’s consider the case for
n = 4
andk = 14
.- We know there are
24
permutations (n!
). - Because the numbers are in sequence from
1
ton
, we have the next permutations:- 1 + permutations of {2, 3, 4} -> (3! = 6) -> (1234, 1243, 1324, 1342, 1423, 1432) -> Permutations
1
to6
- 2 + permutations of {1, 3, 4} -> (3! = 6) -> (2134, 2143, 2314, 2341, 2413, 2431) -> Permutations
7
to12
- 3 + permutations of {1, 2, 4} -> (3! = 6) -> (3124, 3142, 3214, 3241, 3412, 3421) -> Permutations
13
to18
- 4 + permutations of {1, 2, 3} -> (3! = 6) -> (4123, 4132, 4213, 4231, 4312, 4321) -> Permutations
19
to24
- 1 + permutations of {2, 3, 4} -> (3! = 6) -> (1234, 1243, 1324, 1342, 1423, 1432) -> Permutations
- From the previous, we know that the
14th
permutation (k = 14
) starts with3
, so we are at the13th
permutation. - Then to calculate the next number we repeat the process with the rest of the numbers:
- 1 + permutations of {2, 4} -> (2! = 2) -> (124, 142) -> Permutations
13
to14
- 2 + permutations of {1, 4} -> (2! = 2) -> (214, 241) -> Permutations
15
to16
- 4 + permutations of {1, 2} -> (2! = 2) -> (412, 421) -> Permutations
17
to18
- 1 + permutations of {2, 4} -> (2! = 2) -> (124, 142) -> Permutations
- From the previous, we know the next number is
1
, so, we repeat the process:- 2 + permutation of {4} -> (1! = 1) -> (24) -> Permutations
13
. - 4 + permutation of {2} -> (1! = 1) -> (42) -> Permutations
14
.
- 2 + permutation of {4} -> (1! = 1) -> (24) -> Permutations
- From the previous, we know the next number is
4
, so, we repeat the process:- 2 + permutation of {} -> (0! = 1) -> (2) -> Permutations
14
.
- 2 + permutation of {} -> (0! = 1) -> (2) -> Permutations
- From the previous, we know the next number is
2
. There are no more numbers left, so, the algorithm ends.
- We know there are
The 14th
permutation is: 3142
.
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
string getPermutation(int n, int k) {
string permutation = "";
vector<bool> v(n+1,false);
vector<int> f(n+1, 1);
for (int i = 2; i <= n; i++)
f[i] = f[i-1] * i;
k--;
for(int i = 1; i <= n; i++){
int x = k/f[n-i];
int j;
k -= x * f[n-i];
for(j = 1; j <= n; j++) {
if (!v[j] && x==0)
break;
if (!v[j])
x--;
}
if (j<=n)
v[j] = true;
permutation += to_string(j);
}
return permutation;
}
};