1. Problem Statement (Simple Explanation)
You have the set: [1, 2, 3, ..., n]
This set has n! permutations. If you list them in lexicographic (sorted) order, you get a sequence:
For n = 3, the permutations in order are:
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, you must return the k-th permutation in this lexicographic sequence (1-indexed).
2. Examples
Example 1:
Input: n = 3, k = 3
Permutations:
"123"
"132"
"213" ← 3rd
Output: "213"
Example 2:
Input: n = 4, k = 9
Permutations of [1,2,3,4] in lexicographic order:
1234
1243
1324
1342
1423
1432
2134
2143
2314 ← 9th
...
Output: "2314"
Example 3:
Input: n = 3, k = 1
First permutation is "123".
Output: "123"
3. Approach – Factorial Number System (Direct k-th Permutation)
Instead of generating all permutations (which is too slow), we compute the k-th permutation directly using factorial arithmetic.
Key Observations:
There are n! permutations.
For a fixed first digit:
There are (n-1)! permutations for any choice of the first digit.
If we have a sorted list of remaining digits, the first digit of the k-th permutation is determined by: index = (k-1) / (n-1)!
Then:
Pick the digit at index in the remaining digits list.
Remove that digit.
Update k to be the position within that block: k = k - index * (n-1)!
Repeat this for each position.
We treat k as 1-based, so we subtract 1 initially or adjust formulas appropriately.
Step-by-step Example – n = 4, k = 9
Digits: [1, 2, 3, 4]
Factorials: 3! = 6, 2! = 2, 1! = 1
First position:
Block size = 3! = 6
k = 9
index = (k-1)/6 = (9-1)/6 = 8/6 = 1
So first digit is digits[1] = 2
Remove 2 → digits = [1,3,4]
New k = k - index * 6 = 9 - 1*6 = 3
Result: "2"
Second position:
Now n = 3, block size = 2! = 2
k = 3
index = (k-1)/2 = (3-1)/2 = 2/2 = 1
digit = digits[1] = 3
Remove 3 → digits = [1,4]
New k = 3 - 1*2 = 1
Result: "23"
Third position:
n = 2, block size = 1! = 1
k = 1
index = (k-1)/1 = 0
digit = digits[0] = 1
Remove 1 → digits = [4]
New k = 1 - 0*1 = 1
Result: "231"
Fourth position:
Only one digit left: 4
Result: "2314"
Algorithm (High-level):
Create a list digits = [1, 2, ..., n].
Precompute factorials fact[i] = i! for i = 0..n.
Adjust k to be 0-based: k--.
For position from n down to 1:
Let blockSize = fact[pos-1].
index = k / blockSize.
Append digits[index] to result and remove it from digits.
k = k % blockSize.
Convert result list to a string.
Pseudo-code:
Complexity:
Building factorials: O(n)
Looping n times, each removing an element from list digits:
If implemented with a list/ArrayList and remove by index: O(n²) in worst case (but n <= 9 so it’s negligible).
Overall: effectively O(n²) but for n ≤ 9, this is very fast.
Space: O(n) for factorials, digits, and result.
4. Java code
7. Python code
8. JavaScript code
Comments
Post a Comment