Permutation Sequence

                                            
class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> nums;
        for(int i = 1; i <= n; i++) {
            nums.push_back(i);
        }
        
        string result;
        int fac = 1;
        for(int i = 2; i < n; i++) {
            fac *= i;
        }
        k--;
        
        while(n > 0) {
            int index = k / fac;
            result += to_string(nums[index]);
            nums.erase(nums.begin() + index);
            k %= fac;
            if(n > 1) {
                fac /= (n-1);
            }
            n--;
        }
        
        return result;
    }
};

                                            
class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new ArrayList<>();
        int[] factorial = new int[n + 1];
        StringBuilder sb = new StringBuilder();
        
        int sum = 1;
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            sum *= i;
            factorial[i] = sum;
            numbers.add(i);
        }
        
        k--;
        
        for (int i = 1; i <= n; i++) {
            int index = k / factorial[n - i];
            sb.append(numbers.get(index));
            numbers.remove(index);
            k -= index * factorial[n - i];
        }
        
        return sb.toString();
    }
}

                                            
class Solution(object):
    def getPermutation(self, n, k):
        def getFactorial(num):
            result = 1
            for i in range(1, num+1):
                result *= i
            return result
        
        nums = [str(i) for i in range(1, n+1)]
        factorial = getFactorial(n)
        k -= 1
        result = ""
        
        while n > 0:
            factorial //= n
            index = k // factorial
            result += nums.pop(index)
            k %= factorial
            n -= 1
        
        return result

                                            
public class Solution {
    public string GetPermutation(int n, int k) {
        List<int> numbers = new List<int>();
        for (int i = 1; i <= n; i++) {
            numbers.Add(i);
        }
        
        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        
        k--;
        StringBuilder sb = new StringBuilder();
        
        for (int i = 1; i <= n; i++) {
            int index = k / factorial[n - i];
            sb.Append(numbers[index]);
            numbers.RemoveAt(index);
            k -= index * factorial[n - i];
        }
        
        return sb.ToString();
    }
}

                                            
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function(n, k) {
    const nums = Array.from({ length: n }, (_, index) => index + 1);
    let result = '';
    k--;
    
    while (n > 0) {
        const factorial = factorialize(n - 1);
        const index = Math.floor(k / factorial);
        result += nums[index];
        nums.splice(index, 1);
        k %= factorial;
        n--;
    }
    
    return result;
    
    function factorialize(num) {
        if (num <= 1) {
            return 1;
        }
        return num * factorialize(num - 1);
    }
};

                                            
function getPermutation(n: number, k: number): string {
    const nums = Array.from({ length: n }, (_, index) => index + 1);
    let result = '';
    
    const factorial = (num: number): number => {
        let res = 1;
        for (let i = 1; i <= num; i++) {
            res *= i;
        }
        return res;
    };
    
    k--;
    while (nums.length > 0) {
        const fact = factorial(nums.length - 1);
        const index = Math.floor(k / fact);
        result += String(nums[index]);
        nums.splice(index, 1);
        k %= fact;
    }
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer $n
     * @param Integer $k
     * @return String
     */
    function getPermutation($n, $k) {
        $fact = 1;
        $nums = [];
        for ($i = 1; $i <= $n; $i++) {
            $fact *= $i;
            $nums[] = $i;
        }
        $k--;
        $result = "";
        
        while ($n > 0) {
            $fact = $fact / $n;
            $index = (int)($k / $fact);
            $result .= strval($nums[$index]);
            array_splice($nums, $index, 1);
            $k %= $fact;
            $n--;
        }
        
        return $result;
    }
}

                                            
class Solution {
    /**
     * @param Integer $n
     * @param Integer $k
     * @return String
     */
    func getPermutation(_ n: Int, _ k: Int) -> String {
        var fact = 1
        for i in 1...n {
            fact *= i
        }
        
        var nums = [Int](1...n)
        var k = k - 1
        
        var result = ""
        for i in 0..<n {
            fact = fact / (n - i)
            let index = k / fact
            k = k % fact
            
            result += String(nums.remove(at: index))
        }
        
        return result
    }
}

                                            
class Solution {
  String getPermutation(int n, int k) {
    List<int> numbers = List.generate(n, (index) => index + 1);

    List<int> factorials = [1];
    for (int i = 1; i <= n; i++) {
      factorials.add(factorials[i - 1] * i);
    }

    k--;

    String result = '';
    for (int i = n - 1; i >= 0; i--) {
      int index = k ~/ factorials[i];
      k %= factorials[i];
      result += numbers[index].toString();
      numbers.removeAt(index);
    }

    return result;
  }
}

                                            
func getPermutation(n int, k int) string {
    factorial := make([]int, n+1)
    factorial[0] = 1
    nums := make([]int, n)
    for i := 1; i <= n; i++ {
        factorial[i] = factorial[i-1] * i
        nums[i-1] = i
    }
    
    k-- 
    var result strings.Builder
    for i := 1; i <= n; i++ {
        index := k / factorial[n-i]
        result.WriteString(strconv.Itoa(nums[index]))
        nums = append(nums[:index], nums[index+1:]...)
        k -= index * factorial[n-i]
    }
    
    return result.String()
}

                                            
# @param {Integer} n
# @param {Integer} k
# @return {String}
def get_permutation(n, k)
    nums = (1..n).to_a
    result = ""
    k -= 1
    
    while n > 0
        n -= 1
        index = k / factorial(n)
        k %= factorial(n)
        result += nums.delete_at(index).to_s
    end
    
    result
end

def factorial(n)
    n <= 1 ? 1 : n * factorial(n - 1)
end

                                            
impl Solution {
    pub fn get_permutation(n: i32, k: i32) -> String {
        let mut nums: Vec<i32> = (1..=n).collect();
        let mut factorial: Vec<i32> = vec![1; n as usize];

        for i in 1..n as usize {
            factorial[i] = factorial[i - 1] * i as i32;
        }

        let mut k = k - 1;
        let mut result = String::new();

        for i in (0..n as usize).rev() {
            let index = (k / factorial[i]) as usize;
            k %= factorial[i];
            result.push_str(&nums[index].to_string());
            nums.remove(index);
        }

        result
    }
}

To solve this coding challenge, we need to determine the kth permutation sequence of the numbers from 1 to n, arranged in a specific order. The task requires us to generate permutations efficiently without listing all permutations explicitly due to the factorial growth rate in the number of permutations. Below are the logical steps and pseudocode:

Explanation

Understanding the problem requires knowledge about permutations and factorials. Specifically, in total there are \( n! \) permutations for a sequence from 1 to n. The key insight is that we can determine the kth permutation by successively deciding the leading digit and adjusting the sequence accordingly.

Factorial Calculation : First, we need a helper function to calculate the factorial of a number, which helps in determining the number of permutations starting with a particular digit.
Adjust Index : Convert k from a 1-based index to a 0-based index for easier calculation.
Digit Selection : At each step, decide which digit will be the next in the permutation by dividing
k

by the factorial of remaining digits to determine the block it falls into.
Update Sequence : Remove the selected digit from the pool and reduce k accordingly.
Loop Until Done : Repeat the above process until all digits are selected and sequenced.

Detailed Steps in Pseudocode

Calculate Factorial :

Create a helper function
getFactorial(num)

that returns the factorial of
num

.

Initial Setup :

Create a list
nums

of strings representing numbers from 1 to n.
Compute the factorial of n using
getFactorial(n)

.
Decrement k by 1 to make it zero-based (for easier indexing in a list/array).

Select Digits to Form Permutation :

Initialize an empty string
result

to build the permutation.
While n > 0:

Compute
factorial = factorial // n

. This gives the number of permutations for the remaining digits.
Determine the index using
index = k // factorial

.
Append the number at
nums[index]

to the
result

.
Update
k

using
k = k % factorial

.
Remove the used number from
nums

.
Decrement n.

Return Result .

Pseudocode

                                            
# Function to calculate the factorial of a number.
function getFactorial(num):
    result = 1
    for i from 1 to num:
        result *= i
    return result

# Function to get the kth permutation sequence.
function getPermutation(n, k):
    # Step 1: Initialize the numbers list and calculate the initial factorial
    nums = [str(i) for i in range(1, n + 1)]
    factorial = getFactorial(n)
    k -= 1  # Step 2: Convert to zero-based index
    result = ""  # Step 3: Initialize the result string

    # Step 4: Form the kth permutation by selecting digits
    while n > 0:
        factorial //= n  # Update factorial to the factorial for (n-1)
        index = k // factorial  # Determine the index of the next digit
        result += nums[index]  # Append that digit to result
        k %= factorial  # Update k to the new relative index
        nums.remove(nums[index])  # Remove used digit from the list
        n -= 1  # Decrement n

    # Step 5: Return the permutation as a string
    return result

# Example function calls
getPermutation(3, 3)  # Expected output "213"
getPermutation(4, 9)  # Expected output "2314"
getPermutation(3, 1)  # Expected output "123"

With this detailed explanation and pseudocode, we can thoroughly understand the steps necessary to derive the kth permutation and implement our solution effectively.