Permutation Sequence

Given a set of distinct numbers and an integer k, find the k-th lexicographically smallest permutation of these numbers. Understanding permutations and their ordering is fundamental in combinatorics and computer science, with applications in areas like algorithm design and data analysis.

Problem Description

You are given a set of n distinct numbers, typically represented as the integers from 1 to n. Your task is to generate all possible permutations of these n numbers and then find the k-th permutation in lexicographical order. Lexicographical order means the permutations are sorted as if they were words in a dictionary.

Requirements:

1. Given an integer n (representing the size of the set of numbers, which are assumed to be 1 to n).
2. Given an integer k (representing the index of the permutation to find, 1-based).
3. Return the k-th permutation as a sequence of numbers.

Expected Behavior:

The function should compute the k-th permutation efficiently. The numbers are considered to be from the set {1, 2, ..., n}.

Edge Cases:

• n = 1: The only permutation is [1].
• k = 1: This should return the first permutation in lexicographical order (which is [1, 2, ..., n]).
• k being the total number of permutations (n!).

Examples

Example 1:

Input: n = 3, k = 3
Output: "213"
Explanation: The permutations of [1, 2, 3] in lexicographical order are:
"123" (k=1)
"132" (k=2)
"213" (k=3)
"231" (k=4)
"312" (k=5)
"321" (k=6)
The 3rd permutation is "213".

Example 2:

Input: n = 4, k = 9
Output: "2314"
Explanation: The permutations of [1, 2, 3, 4] are:
1234 (1)  1243 (2)  1324 (3)  1342 (4)  1423 (5)  1432 (6)
2134 (7)  2143 (8)  2314 (9)
...
The 9th permutation is "2314".

Example 3:

Input: n = 2, k = 2
Output: "21"
Explanation: The permutations of [1, 2] are:
"12" (k=1)
"21" (k=2)
The 2nd permutation is "21".

Constraints

• 1 <= n <= 9
• 1 <= k <= n! (where n! is the factorial of n)
• The input n will be an integer.
• The input k will be an integer.
• The output should be a string representation of the permutation.

Notes

• You can pre-calculate factorials or compute them as needed.
• Consider how to determine which number comes first, then which comes second, and so on, without generating all permutations.
• A mathematical approach involving factorials is likely more efficient than brute-force generation.
• The problem statement implies the numbers are 1, 2, ..., n. You will need to manage which numbers have already been used.