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:
- “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”
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:
- Create a list of digits from 1 to n.
- Create a factorials list, which stores the factorial of integers from 0 to n.
- Decrement k by 1 (0-based indexing).
- Create an empty result string.
- 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. - 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 Listnums = 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 vectornums; 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 Listnums = 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(); } }