Home Permutation Sequence
Post
Cancel

LeetCode #60: Permutation Sequence (C/C++).

hard

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 and k = 14.
    • We know there are 24 permutations (n!).
    • Because the numbers are in sequence from 1 to n, we have the next permutations:
      • 1 + permutations of {2, 3, 4} -> (3! = 6) -> (1234, 1243, 1324, 1342, 1423, 1432) -> Permutations 1 to 6
      • 2 + permutations of {1, 3, 4} -> (3! = 6) -> (2134, 2143, 2314, 2341, 2413, 2431) -> Permutations 7 to 12
      • 3 + permutations of {1, 2, 4} -> (3! = 6) -> (3124, 3142, 3214, 3241, 3412, 3421) -> Permutations 13 to 18
      • 4 + permutations of {1, 2, 3} -> (3! = 6) -> (4123, 4132, 4213, 4231, 4312, 4321) -> Permutations 19 to 24
    • From the previous, we know that the 14th permutation (k = 14) starts with 3, so we are at the 13th 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 to 14
      • 2 + permutations of {1, 4} -> (2! = 2) -> (214, 241) -> Permutations 15 to 16
      • 4 + permutations of {1, 2} -> (2! = 2) -> (412, 421) -> Permutations 17 to 18
    • 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.
    • From the previous, we know the next number is 4, so, we repeat the process:
      • 2 + permutation of {} -> (0! = 1) -> (2) -> Permutations 14.
    • From the previous, we know the next number is 2. There are no more numbers left, so, the algorithm ends.

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;
  }
};
This post is licensed under CC BY 4.0 by the author.

Wildcard Matching

Linked List with C++