# 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++) {
}

// 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++) {
}

// 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();
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]