Permutation Sequence

LeetCode Problem #60 (Medium)

Problem Statement

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labelling all of the permutations in order, we get the following sequence for n = 3:

1. "123"

2. "132"

3. "213"

4. "231"

5. "312"

6. "321"

Given n and k, return the kth permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.

• Given k will be between 1 and n! inclusive.

Testcases

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Prerequisite Knowledge

Permutation

The different ways in which a collection of items can be arranged or ordered is known as permutation. A string of length n can have n! different permutations.

For instance, consider the string "ABC". There are n! different permutations of this string wherein, each arrangement uses exactly the same elements in the original string. Since there are three elements in this string, there are 3! = 6 possible permutations, including "ABC".

1. "ABC"

2. "ACB"

3. "BAC"

4. "BCA"

5. "CAB"

6. "CBA"

Source: https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Problem Explanation

We are given two input values, n and k. n corresponds to the number of elements that we must consider, taken from the given set, [1,2,3,...,n]. The permutations of the n elements will be ordered sequentially. k corresponds to the kth permutation that is generated among all of the ordered permutations.

For example, if n = 4 and k = 9 the elements to consider are: {1, 2, 3, 4}

The permutations can be calculated as:

1. 1 + permutations{2, 3, 4}-> 6 elements (1 - 6)

2. 2 + permutations{1, 3, 4}-> 6 elements (7 - 12)

3. 3 + permutations{1, 2, 4}-> 6 elements (13 - 18)

4. 4 + permutations{1, 2, 3}-> 6 elements (19 - 24)

The first element is fixed and we have (n-1)! unique ways to arrange the remaining three elements. Therefore, there are a total of 24 different permutations for the given set of numbers. If we wanted to find the 9th element, as stipulated by the k value, we would have to search in the second set of six elements since 6 < 9 < 12.

Using this logic, we must find the correct permutation according to the given values of n and k.

Algorithm

Iterative Math Approach

1. Calculate the factorials of each number from 1 to 9 and store it in an array.

2. Store all of the available characters within the given range in a character array by adding '0' to each number.

3. Create an empty result string.

4. Calculate the k value considering the possibility of k > (n-1)! and therefore taking modulus with factorial[n] to prevent this.

5. Iteratively determine which elements must be in the sequence:

   a. Find the position of the character to add.

   b. Append the character to the resultant string.

   c. Remove the element which has already been considered.

   d. Find the new k value for the next iteration.

6. When the value of n = 0, return the resultant string.

Code

string getPermutation(int n, int k) {
    // Calculate the factorials between 1 and 9
    int factorials[10] = {1};
    for(int i = 1; i < 10; i++) {
        factorials[i] = i * factorials[i-1];
    } 
    
    // Store the available characters
    vector<char> nums;
    for(int i = 0; i < n; i++) {
        // Array index starts at 0, Element value starts from 1
        nums.push_back('0' + i + 1);
    }
    
    string res = "";
    // Calculate k value
    int k_val = (k-1) % factorials[n];
    while(n) {
        // Find the position of the character to add
        int pos = k_val / factorials[n-1];
        // Append the character to the resultant string
        res += nums[pos];
        // Remove the elements that have already been considered
        nums.erase(nums.begin() + pos);
        // Find the new k value
        k_val %= factorials[n-1];
        // Exit when n = 0
        n--;
    }
    return res;
}