Description:
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"Solution in Python:
To solve this problem, we need to determine the k-th permutation of the sequence [1, 2, 3, …, n] in lexicographical order. This can be achieved by utilizing the properties of factorials to directly compute the k-th permutation without generating all permutations.
Steps to solve the problem:
- Calculate Factorials: Compute the factorial of each number from 1 to n-1. These factorials will help in determining the positions of the elements in the permutation.
- Adjust k: Since the sequence indexing is 1-based, but Python uses 0-based indexing, decrement k by 1.
- Generate Permutation:
- Initialize a list of numbers from 1 to n.
- Determine the appropriate element to place at each position by using the factorial values to skip groups of permutations.
- Remove the selected element from the list of numbers to prevent reuse.
- Construct the Result: Append each selected element to the result string to form the final k-th permutation.
Python
class Solution:
def getPermutation(self, n: int, k: int) -> str:
# Step 1: Calculate factorials
factorials = [1] * n
for i in range(1, n):
factorials[i] = factorials[i - 1] * i
# Step 2: Adjust k to be zero-indexed
k -= 1
# Step 3: Generate the permutation
numbers = list(range(1, n + 1))
result = []
for i in range(n, 0, -1):
# Determine which number should be at the current position
idx = k // factorials[i - 1]
result.append(str(numbers[idx]))
# Remove used number from the list
numbers.pop(idx)
# Update k for the next position
k %= factorials[i - 1]
# Step 4: Construct the final permutation string
return ''.join(result)Solution in Javascript:
JavaScript
/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var getPermutation = function(n, k) {
// Step 1: Calculate factorials
let factorials = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
factorials[i] = factorials[i - 1] * i;
}
// Step 2: Adjust k to be zero-indexed
k -= 1;
// Step 3: Generate the permutation
let numbers = Array.from({length: n}, (_, i) => i + 1); // [1, 2, 3, ..., n]
let result = '';
for (let i = n; i > 0; i--) {
// Determine which number should be at the current position
let idx = Math.floor(k / factorials[i - 1]);
result += numbers[idx];
// Remove used number from the list
numbers.splice(idx, 1);
// Update k for the next position
k %= factorials[i - 1];
}
// Step 4: Return the final permutation string
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public String getPermutation(int n, int k) {
// Step 1: Calculate factorials
int[] factorials = new int[n];
factorials[0] = 1;
for (int i = 1; i < n; i++) {
factorials[i] = factorials[i - 1] * i;
}
// Step 2: Adjust k to be zero-indexed
k -= 1;
// Step 3: Generate the permutation
List<Integer> numbers = new ArrayList<>();
for (int i = 1; i <= n; i++) {
numbers.add(i);
}
StringBuilder result = new StringBuilder();
for (int i = n; i > 0; i--) {
// Determine which number should be at the current position
int idx = k / factorials[i - 1];
result.append(numbers.get(idx));
// Remove used number from the list
numbers.remove(idx);
// Update k for the next position
k %= factorials[i - 1];
}
// Step 4: Return the final permutation string
return result.toString();
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
using System.Text;
public class Solution {
public string GetPermutation(int n, int k) {
// Step 1: Calculate factorials
int[] factorials = new int[n];
factorials[0] = 1;
for (int i = 1; i < n; i++) {
factorials[i] = factorials[i - 1] * i;
}
// Step 2: Adjust k to be zero-indexed
k -= 1;
// Step 3: Generate the permutation
List<int> numbers = new List<int>();
for (int i = 1; i <= n; i++) {
numbers.Add(i);
}
StringBuilder result = new StringBuilder();
for (int i = n; i > 0; i--) {
// Determine which number should be at the current position
int idx = k / factorials[i - 1];
result.Append(numbers[idx]);
// Remove used number from the list
numbers.RemoveAt(idx);
// Update k for the next position
k %= factorials[i - 1];
}
// Step 4: Return the final permutation string
return result.ToString();
}
}