Solution For Permutation Sequence

Problem statement:

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:

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.

Example 1:

Input: n = 3, k = 3
Output: “213”

Example 2:

Input: n = 4, k = 9
Output: “2314”

Solution:

In this problem, we need to find the kth permutation sequence of [1,2,3,…,n]. We can approach this problem by finding the digits from left to right.

Let’s consider an example: n=4, k=9.
The total number of permutations of [1,2,3,4] is 4! = 24, which means that there are 24 possible sequences. The first digit can be selected from [1,2,3,4], which means that there are 4 possible options (i.e, we have 4 choices for the first digit). If we fix the first digit, we are left with (n-1)! possible permutations for the remaining digits. Therefore, there are (4-1)! = 6 possible permutations for the remaining three digits. Similarly, there are (3-1)! = 2 possible permutations for the remaining two digits and 1 possible permutation for the last digit.

We can use this approach to find the kth permutation sequence. We start by finding the index of the first digit in the sequence. The index is given by (k-1)/(n-1)!, which gives the number of blocks of (n-1)! permutations that we need to skip to reach the kth sequence. We subtract 1 from this index to get the index of the actual digit in the list. We then remove this digit from the list and repeat the process for the remaining digits.

Here is the detailed algorithm:

1. Create a list of digits from 1 to n.
2. Create a factorials list, which stores the factorial of integers from 0 to n.
3. Decrement k by 1 (0-based indexing).
4. Create an empty result string.
5. Repeat n times:
   a. Find the index of the first digit in the list using the formula: (k // factorials[n-1]).
   b. Add the digit at the index to the result string.
   c. Remove the digit from the list.
   d. Update k using the formula: k = k % factorials[n-1].
   e. Decrement n by 1.
6. Return the result string.

Here is the Python code for the above algorithm:

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

    k -= 1
    result = ""
    for i in range(n, 0, -1):
        index = k // factorials[i-1]
        result += nums[index]
        nums.pop(index)
        k %= factorials[i-1]

    return result

Time Complexity: O(n^2)
Space Complexity: O(n)

Step by Step Implementation For Permutation Sequence

The problem can be found here: https://leetcode.com/problems/permutation-sequence/

public class Solution {
    public String getPermutation(int n, int k) {
        
        // create a list of numbers to get permutations of
        List nums = new ArrayList();
        for (int i = 1; i <= n; i++) {
            nums.add(i);
        }
        
        // calculate the factorial of n
        int factorial = 1;
        for (int i = 2; i <= n; i++) {
            factorial *= i;
        }
        
        // set k to be within the bounds of factorial
        k = k % factorial;
        
        // if k is 0, set it to the highest permutation
        if (k == 0) {
            k = factorial;
        }
        
        // initialize our result string
        String result = "";
        
        // loop through nums until it is empty
        while (!nums.isEmpty()) {
            
            // calculate the factorial of n - 1
            factorial = factorial / n;
            
            // find the index of the next number in the permutation
            int index = (k - 1) / factorial;
            
            // append the number at that index to our result
            result += nums.get(index);
            
            // remove the number at that index from the list
            nums.remove(index);
            
            // update k to be the next number in the permutation
            k = k - (index * factorial);
            
            // decrement n
            n--;
        }
        
        // return the result
        return result;
    }
}

The problem is as follows:

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.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:

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

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

def getPermutation(n: int, k: int) -> str:
    
    # create a list of numbers to get permutations from
    nums = [i for i in range(1, n+1)]
    
    # calculate factorial of n
    factorial = 1
    for i in range(2, n+1):
        factorial *= i
        
    # initialize an empty string to store permutation
    permutation = ""
    
    # keep track of current index
    index = 0
    
    # keep track of current factorial
    curr_factorial = factorial
    
    # while there are still numbers to get permutations from
    while nums:
        
        # get the index of the number to be added to permutation
        # based on value of k and current factorial
        index = k // curr_factorial
        
        # if k is greater than the current factorial,
        # reduce k by the current factorial
        if k > curr_factorial:
            k -= curr_factorial * index
        
        # otherwise, k is equal to the current factorial
        else:
            # reduce k by the current factorial
            k -= curr_factorial
            
            # if k is now 0, set index to last element in nums list
            if k == 0:
                index = len(nums) - 1
        
        # add the number at the calculated index to the permutation
        permutation += str(nums[index])
        
        # remove the number from the nums list
        nums.pop(index)
        
        # update current factorial
        curr_factorial //= len(nums)
        
    return permutation

var getPermutation = function(n, k) {
    // create an array of numbers 1 to n
    let nums = [];
    for (let i = 1; i <= n; i++) {
        nums.push(i);
    }
    
    // calculate factorial of n
    let factorial = 1;
    for (let i = 2; i <= n; i++) {
        factorial *= i;
    }
    
    // create a result string
    let result = "";
    
    // loop through the array, getting the correct number for each position
    // and removing it from the array so it can't be used again
    for (let i = 0; i < n; i++) {
        // get the index of the number we want for this position
        let index = Math.floor((k - 1) / (factorial / n));
        
        // add the number at that index to the result
        result += nums[index];
        
        // remove the number at that index from the array
        nums.splice(index, 1);
        
        // update k to be the value for the next position
        k -= index * (factorial / n);
        
        // update factorial
        factorial /= n;
        
        // decrement n
        n--;
    }
    
    return result;
};

class Solution {
public:
    string getPermutation(int n, int k) {
        //create a vector of numbers 1 to n
        vector nums;
        for(int i = 1; i <= n; i++)
            nums.push_back(i);
        
        //calculate factorial of n
        int fact = 1;
        for(int i = 2; i <= n; i++)
            fact *= i;
        
        //set k to be within range
        k--;
        
        //calculate sequence
        string seq = "";
        for(int i = 0; i < n; i++){
            fact /= (n-i);
            int index = k/fact;
            k -= index*fact;
            
            seq += to_string(nums[index]);
            nums.erase(nums.begin() + index);
        }
        
        return seq;
    }
};

public class Solution {
    public string GetPermutation(int n, int k) {
        
        // list to store all numbers from 1 to n
        List nums = new List();
        for (int i = 1; i <= n; i++) {
            nums.Add(i);
        }
        
        // factorial array to store factorials of numbers from 0 to n-1
        int[] factorials = new int[n];
        factorials[0] = 1;
        for (int i = 1; i < n; i++) {
            factorials[i] = factorials[i-1] * i;
        }
        
        // build the permutation string
        StringBuilder sb = new StringBuilder();
        k--;  // change k to be index
        for (int i = 0; i < n; i++) {
            int index = k / factorials[n-1-i];
            sb.Append(nums[index]);
            nums.RemoveAt(index);
            k -= index * factorials[n-1-i];
        }
        
        return sb.ToString();
    }
}