Builds on One Choice per Slot, which you haven’t finished yet.
K-th in Dictionary Order by Block Counting (Unranking, Factorial Number System)
The numbers 1, 2, ..., n can be put in order in n! different ways. Write all of these arrangements as strings and sort them the way a dictionary sorts words. For n = 3 the list is "123", "132", "213", "231", "312", "321", and its entries are numbered from 1.
Given n and a position k in this list, return the arrangement at position k.
123, 132, 213, 231, 312, 321, and its third entry is 213. The first two entries start with 1, so the third is the first one that starts with 2.Count and Skip
rank k in a huge list in dictionary order ➔ at each slot, skip k // block blocks of equal size (k counted from 0) and keep k % block ➔ the k-th item, built one slot at a timek-th item of a huge list sorted in dictionary order (the k-th permutation, route, string or number), or the rank of a given item in that list, and the list is far too long to build: k can reach n!, C(30, 15) or 1015.| 1 | def get_permutation(n: int, k: int) -> str: |
| 2 | """Permutation Sequence: skip whole blocks of arrangements that share the digits chosen so far. |
| 3 | Time: O(N^2) | Space: O(N) |
| 4 | """ |
| 5 | fact = [1] * n # fact[m] = m! |
| 6 | |
| 7 | # 1. Precompute Factorials: |
| 8 | # fact[m] holds m!, the number of arrangements of m items, needed below |
| 9 | # to size each slot's blocks without computing a factorial inside the main loop. |
| 10 | for m in range(1, n): |
| 11 | fact[m] = fact[m - 1] * m |
| 12 | |
| 13 | pool = [str(d) for d in range(1, n + 1)] # unused digits, smallest first |
| 14 | |
| 15 | # 2. Convert the Rank to 0-Based: |
| 16 | # k counts from 1, but k // block below needs the count of arrangements |
| 17 | # that come strictly before the answer, which is k - 1. |
| 18 | k -= 1 |
| 19 | result = [] # digits of the answer, chosen one slot at a time |
| 20 | |
| 21 | # 3. Choose Each Slot by Skipping Whole Blocks: |
| 22 | # Every unused digit starts a block of fact[n - 1 - slot] arrangements |
| 23 | # that share the digits chosen so far; dividing k by that block size |
| 24 | # finds how many whole blocks come before the answer, and the remainder |
| 25 | # becomes the answer's rank inside the chosen block for the next slot. |
| 26 | for slot in range(n): |
| 27 | block = fact[n - 1 - slot] |
| 28 | index = k // block |
| 29 | k %= block |
| 30 | result.append(pool.pop(index)) |
| 31 | return "".join(result) |
k is always the number of arrangements that start with result and come before the answer, so each slot skips exactly k // block whole blocks.Items in dictionary order come in blocks: every arrangement that starts with the same digit sits together, and here every block at a slot holds the same number of arrangements, block = fact[n - 1 - slot]. So the answer's digit for a slot is found without listing anything: skip index = k // block whole blocks, take pool.pop(index), and continue inside the chosen block with k %= block, one slot to the right and one factorial smaller. This is correct because the blocks come in the same order as their first digits and all have the same size, so exactly index of them lie before the answer, and k % block is the answer's rank inside its own block; removing the used digit from pool keeps the next slot's choices in order. The trap is the rank's base: k counts from 1, so subtract 1 first. Without k -= 1, every k that is a multiple of block picks one block too far: n = 3, k = 3 gives "231" instead of "213".
See it run
Count and Skip, step by step
k 9slot -block -index -
The top row is pool, the unused digits in order. The bottom row is result, one cell per slot.
indexthe digit in pool at position k // block, the first digit of the chosen blockappendthe digit just added to result
Start: n = 4 and k = 9. fact = [1, 1, 2, 6] and pool = [1, 2, 3, 4].
Gotcha 1 of 4
- The trap
Gotcha 1: Leaving out
k -= 1Mistakeresult = []Fixk -= 1 result = []What happens:
kcounts from 1, butk // blockneeds the number of arrangements before the answer. That number isk - 1. Withoutk -= 1, everykthat is a multiple ofblockpicks one block too far.Example: n = 3, k = 3Mistake: returns '231'Fix: returns '213'
- You get one arrangement and need the one right after it, changed in place, as in Next Permutation (LC 31): there is no rank to count down. See Next Permutation
- You must return every combination, as in Letter Combinations of a Phone Number (LC 17), not jump to one of them by its rank. See One Choice per Slot
- The
k-th item is thek-th smallest value stored in a sorted structure, as in Kth Smallest Element in a Sorted Matrix (LC 378), not thek-th arrangement built slot by slot. See Kth Smallest - You count how many numbers up to
nhave a property, as in Number of Digit One (LC 233): there is no rankkto reach, so nothing is skipped. See Digit DP
Deep Dive
Blocks of equal size in dictionary order
Dictionary order lists the permutations of 1234 like this: 1234, 1243, 1324, and so on. All permutations that start with the same digit are next to each other. They form one block.
For n = 4 there are 24 permutations. The first 6 start with 1 and end with 1432. The next 6 start with 2 and begin with 2134. Every block at the first slot has the same size, 3! = 6, because the three other digits can be arranged in 6 ways.
In general, the block at a slot holds fact[n - 1 - slot] permutations, where fact[m] is m!. Slot 0 has blocks of fact[n - 1]. The last slot has blocks of fact[0] = 1.
So the digit for a slot can be found by arithmetic. Count how many whole blocks come before the answer. That count is k // block, and it is the position of the digit in pool.
Skipping blocks, traced for n = 4 and k = 9
k counts from 1, so the first line subtracts 1. Now k = 8 is the number of permutations before the answer. The table of fact is [1, 1, 2, 6], and pool is [1, 2, 3, 4].
Slot 0: block = fact[3] = 6. index = 8 // 6 = 1, so one whole block (the permutations that start with 1) is skipped. k becomes 8 % 6 = 2. pool.pop(1) removes 2, and pool is [1, 3, 4].
Slot 1: block = fact[2] = 2. index = 2 // 2 = 1 and k = 0. pool.pop(1) removes 3, and pool is [1, 4].
Slot 2: block = 1, index = 0, k = 0. pool.pop(0) removes 1. Slot 3 removes the last digit, 4. The result is "2314". In the full list, the 9th permutation is 2314.
The skipped blocks have the same size, and they come in the order of their first digits. So exactly index blocks lie before the answer. k % block is the rank of the answer inside its own block, and the next slot repeats the idea with a smaller block.
Why k -= 1 is needed
k // block counts the permutations before the answer, in whole blocks. The answer itself is not counted. The rank k counts the answer too, so the number before it is k - 1.
Take n = 3, k = 3. The list is 123, 132, 213, 231, 312, 321. The third item is 213. With k -= 1, k = 2. Slot 0 has block = 2, index = 1 and k = 0, and the result is "213".
Without it, k = 3, index = 3 // 2 = 1 and k = 1. Slot 1 has block = 1, index = 1, and takes 3. The result is "231", the fourth item.
The error appears whenever k is a multiple of block. For n = 4, k = 6, the answer is 1432, the last permutation of the first block. Without k -= 1, 6 // 6 = 1 skips that block, and the answer starts with 2.
Cost, limits and when blocks are not equal
Building fact costs O(N). Each slot calls pool.pop(index), which shifts the digits after index, so one slot costs O(N). The total time is O(N^2) and the space is O(N), as in the blueprint docstring.
Permutation Sequence (LC 60) limits n to 9 and k to n!, so the numbers are small. Python integers have no limit. In a language with 64-bit integers, 20! is the largest factorial that fits, so a larger n needs a cap on k or a big-number type.
The reverse question also works. The rank of "2314" is the sum of index * fact[n - 1 - slot] over all slots, plus 1. Here the sum is 1 * 6 + 1 * 2 + 0 + 0 = 8, and the rank is 9.
k // block is valid only when all blocks at a slot have the same size. In K-th Smallest in Lexicographical Order (LC 440), the numbers are 1 to n as text. For n = 13, the numbers that start with 1 are 1, 10, 11, 12, 13, which is 5 numbers. The numbers that start with 2 are only 2. Block sizes differ, so you count each prefix's block size in a loop and skip while k is larger than that size.
60-Second Pitch
"The list has n! permutations, so I do not build it. In dictionary order, all permutations with the same first digit form a block, and every block has (n - 1)! items. First I subtract 1 from k, so it counts the permutations before the answer. Then at each slot I compute index = k // block. That is how many whole blocks I skip. I take pool.pop(index) as the next digit and keep k % block for the next slot. The time is O(N^2) because of the pops, and the space is O(N). The idea works only when all blocks have the same size. When they differ, as in K-th Smallest in Lexicographical Order, I count each block's size first."
Common Questions
- Why does
k // blockgive the index of the next digit? All permutations that start with the same digit form one block, and all blocks at a slot have the same size. Blocks come in the order of their first digit. So
k // blockblocks come before the answer, and the answer starts with the digit at that position inpool.- Why do you subtract 1 from
k? kis the rank, counted from 1. The division needs the number of permutations before the answer, which isk - 1. Without the subtraction, akthat is a multiple ofblockpicks the next block.get_permutation(3, 3)would return"231"instead of"213".- What are the time and space complexity?
The time is O(N^2) and the space is
O(N). The factorial table costsO(N), and each of the N slots callspool.pop(index), which shifts up to N digits. A balanced tree over the unused digits can reduce the pops toO(log N).- How do you find the rank of a given permutation?
Run the idea backwards. At each slot,
indexis the position of the digit in the sortedpool. The rank is the sum ofindex * fact[n - 1 - slot], plus 1. For"2314"the sum is 8, so the rank is 9.- When does the idea fail, and what do you do then?
It fails when the blocks at one slot have different sizes. In K-th Smallest in Lexicographical Order (LC 440) with
n = 13, the prefix 1 has 5 numbers and the prefix 2 has 1. Then you count the size of each block, and skip a block whilekis larger than its size.
SWE Reasoning
Spot it
- The problem asks for the
k-th item of a list in dictionary order, or for the rank of an item (Permutation Sequence (LC 60)). - The list is far too long to build, because
kcan reachn!. - All items that share the chosen prefix form a block, and every block at a slot has the same size.
- The answer is built one slot at a time, from an ordered
poolof unused choices.
The invariant, step by step
fact[m]holdsm!,poolholds the unused digits in order, andk -= 1turns the rank into the number of permutations before the answer.- At each slot,
block = fact[n - 1 - slot]is the size of one group of permutations that share the digits chosen so far. index = k // blockis the number of whole blocks before the answer. The digit atpool[index]starts the answer's block.k %= blockis the rank of the answer inside that block.pool.pop(index)removes the digit, so the next slot chooses from unused digits only, in order.- After
nslots,resultholds the digits of thek-th permutation, andkis 0.
Traps
- No
k -= 1. Everykthat is a multiple ofblockselects one block too far. Forn = 3, k = 3the result is"231"instead of"213". - Wrong block size.
fact[n - slot]is the size of the group one slot earlier. It raisesIndexErrorat slot 0. pool[index]instead ofpool.pop(index). The digit stays inpooland can be chosen again. The result forn = 3, k = 3becomes"211".- Blocks of different sizes. In K-th Smallest in Lexicographical Order (LC 440),
k // blockwith one fixed size picks the wrong block.
Practice
Builds on One Choice per Slot, which you haven’t finished yet.
K-th in Dictionary Order by Block Counting (Unranking, Factorial Number System)
The numbers 1, 2, ..., n can be put in order in n! different ways. Write all of these arrangements as strings and sort them the way a dictionary sorts words. For n = 3 the list is "123", "132", "213", "231", "312", "321", and its entries are numbered from 1.
Given n and a position k in this list, return the arrangement at position k.
123, 132, 213, 231, 312, 321, and its third entry is 213. The first two entries start with 1, so the third is the first one that starts with 2.Count and Skip
rank k in a huge list in dictionary order ➔ at each slot, skip k // block blocks of equal size (k counted from 0) and keep k % block ➔ the k-th item, built one slot at a timek-th item of a huge list sorted in dictionary order (the k-th permutation, route, string or number), or the rank of a given item in that list, and the list is far too long to build: k can reach n!, C(30, 15) or 1015.| 1 | def get_permutation(n: int, k: int) -> str: |
| 2 | """Permutation Sequence: skip whole blocks of arrangements that share the digits chosen so far. |
| 3 | Time: O(N^2) | Space: O(N) |
| 4 | """ |
| 5 | fact = [1] * n # fact[m] = m! |
| 6 | |
| 7 | # 1. Precompute Factorials: |
| 8 | # fact[m] holds m!, the number of arrangements of m items, needed below |
| 9 | # to size each slot's blocks without computing a factorial inside the main loop. |
| 10 | for m in range(1, n): |
| 11 | fact[m] = fact[m - 1] * m |
| 12 | |
| 13 | pool = [str(d) for d in range(1, n + 1)] # unused digits, smallest first |
| 14 | |
| 15 | # 2. Convert the Rank to 0-Based: |
| 16 | # k counts from 1, but k // block below needs the count of arrangements |
| 17 | # that come strictly before the answer, which is k - 1. |
| 18 | k -= 1 |
| 19 | result = [] # digits of the answer, chosen one slot at a time |
| 20 | |
| 21 | # 3. Choose Each Slot by Skipping Whole Blocks: |
| 22 | # Every unused digit starts a block of fact[n - 1 - slot] arrangements |
| 23 | # that share the digits chosen so far; dividing k by that block size |
| 24 | # finds how many whole blocks come before the answer, and the remainder |
| 25 | # becomes the answer's rank inside the chosen block for the next slot. |
| 26 | for slot in range(n): |
| 27 | block = fact[n - 1 - slot] |
| 28 | index = k // block |
| 29 | k %= block |
| 30 | result.append(pool.pop(index)) |
| 31 | return "".join(result) |
k is always the number of arrangements that start with result and come before the answer, so each slot skips exactly k // block whole blocks.Items in dictionary order come in blocks: every arrangement that starts with the same digit sits together, and here every block at a slot holds the same number of arrangements, block = fact[n - 1 - slot]. So the answer's digit for a slot is found without listing anything: skip index = k // block whole blocks, take pool.pop(index), and continue inside the chosen block with k %= block, one slot to the right and one factorial smaller. This is correct because the blocks come in the same order as their first digits and all have the same size, so exactly index of them lie before the answer, and k % block is the answer's rank inside its own block; removing the used digit from pool keeps the next slot's choices in order. The trap is the rank's base: k counts from 1, so subtract 1 first. Without k -= 1, every k that is a multiple of block picks one block too far: n = 3, k = 3 gives "231" instead of "213".
See it run
Count and Skip, step by step
k 9slot -block -index -
The top row is pool, the unused digits in order. The bottom row is result, one cell per slot.
indexthe digit in pool at position k // block, the first digit of the chosen blockappendthe digit just added to result
Start: n = 4 and k = 9. fact = [1, 1, 2, 6] and pool = [1, 2, 3, 4].
Gotcha 1 of 4
- The trap
Gotcha 1: Leaving out
k -= 1Mistakeresult = []Fixk -= 1 result = []What happens:
kcounts from 1, butk // blockneeds the number of arrangements before the answer. That number isk - 1. Withoutk -= 1, everykthat is a multiple ofblockpicks one block too far.Example: n = 3, k = 3Mistake: returns '231'Fix: returns '213'
- You get one arrangement and need the one right after it, changed in place, as in Next Permutation (LC 31): there is no rank to count down. See Next Permutation
- You must return every combination, as in Letter Combinations of a Phone Number (LC 17), not jump to one of them by its rank. See One Choice per Slot
- The
k-th item is thek-th smallest value stored in a sorted structure, as in Kth Smallest Element in a Sorted Matrix (LC 378), not thek-th arrangement built slot by slot. See Kth Smallest - You count how many numbers up to
nhave a property, as in Number of Digit One (LC 233): there is no rankkto reach, so nothing is skipped. See Digit DP
Deep Dive
Blocks of equal size in dictionary order
Dictionary order lists the permutations of 1234 like this: 1234, 1243, 1324, and so on. All permutations that start with the same digit are next to each other. They form one block.
For n = 4 there are 24 permutations. The first 6 start with 1 and end with 1432. The next 6 start with 2 and begin with 2134. Every block at the first slot has the same size, 3! = 6, because the three other digits can be arranged in 6 ways.
In general, the block at a slot holds fact[n - 1 - slot] permutations, where fact[m] is m!. Slot 0 has blocks of fact[n - 1]. The last slot has blocks of fact[0] = 1.
So the digit for a slot can be found by arithmetic. Count how many whole blocks come before the answer. That count is k // block, and it is the position of the digit in pool.
Skipping blocks, traced for n = 4 and k = 9
k counts from 1, so the first line subtracts 1. Now k = 8 is the number of permutations before the answer. The table of fact is [1, 1, 2, 6], and pool is [1, 2, 3, 4].
Slot 0: block = fact[3] = 6. index = 8 // 6 = 1, so one whole block (the permutations that start with 1) is skipped. k becomes 8 % 6 = 2. pool.pop(1) removes 2, and pool is [1, 3, 4].
Slot 1: block = fact[2] = 2. index = 2 // 2 = 1 and k = 0. pool.pop(1) removes 3, and pool is [1, 4].
Slot 2: block = 1, index = 0, k = 0. pool.pop(0) removes 1. Slot 3 removes the last digit, 4. The result is "2314". In the full list, the 9th permutation is 2314.
The skipped blocks have the same size, and they come in the order of their first digits. So exactly index blocks lie before the answer. k % block is the rank of the answer inside its own block, and the next slot repeats the idea with a smaller block.
Why k -= 1 is needed
k // block counts the permutations before the answer, in whole blocks. The answer itself is not counted. The rank k counts the answer too, so the number before it is k - 1.
Take n = 3, k = 3. The list is 123, 132, 213, 231, 312, 321. The third item is 213. With k -= 1, k = 2. Slot 0 has block = 2, index = 1 and k = 0, and the result is "213".
Without it, k = 3, index = 3 // 2 = 1 and k = 1. Slot 1 has block = 1, index = 1, and takes 3. The result is "231", the fourth item.
The error appears whenever k is a multiple of block. For n = 4, k = 6, the answer is 1432, the last permutation of the first block. Without k -= 1, 6 // 6 = 1 skips that block, and the answer starts with 2.
Cost, limits and when blocks are not equal
Building fact costs O(N). Each slot calls pool.pop(index), which shifts the digits after index, so one slot costs O(N). The total time is O(N^2) and the space is O(N), as in the blueprint docstring.
Permutation Sequence (LC 60) limits n to 9 and k to n!, so the numbers are small. Python integers have no limit. In a language with 64-bit integers, 20! is the largest factorial that fits, so a larger n needs a cap on k or a big-number type.
The reverse question also works. The rank of "2314" is the sum of index * fact[n - 1 - slot] over all slots, plus 1. Here the sum is 1 * 6 + 1 * 2 + 0 + 0 = 8, and the rank is 9.
k // block is valid only when all blocks at a slot have the same size. In K-th Smallest in Lexicographical Order (LC 440), the numbers are 1 to n as text. For n = 13, the numbers that start with 1 are 1, 10, 11, 12, 13, which is 5 numbers. The numbers that start with 2 are only 2. Block sizes differ, so you count each prefix's block size in a loop and skip while k is larger than that size.
60-Second Pitch
"The list has n! permutations, so I do not build it. In dictionary order, all permutations with the same first digit form a block, and every block has (n - 1)! items. First I subtract 1 from k, so it counts the permutations before the answer. Then at each slot I compute index = k // block. That is how many whole blocks I skip. I take pool.pop(index) as the next digit and keep k % block for the next slot. The time is O(N^2) because of the pops, and the space is O(N). The idea works only when all blocks have the same size. When they differ, as in K-th Smallest in Lexicographical Order, I count each block's size first."
Common Questions
- Why does
k // blockgive the index of the next digit? All permutations that start with the same digit form one block, and all blocks at a slot have the same size. Blocks come in the order of their first digit. So
k // blockblocks come before the answer, and the answer starts with the digit at that position inpool.- Why do you subtract 1 from
k? kis the rank, counted from 1. The division needs the number of permutations before the answer, which isk - 1. Without the subtraction, akthat is a multiple ofblockpicks the next block.get_permutation(3, 3)would return"231"instead of"213".- What are the time and space complexity?
The time is O(N^2) and the space is
O(N). The factorial table costsO(N), and each of the N slots callspool.pop(index), which shifts up to N digits. A balanced tree over the unused digits can reduce the pops toO(log N).- How do you find the rank of a given permutation?
Run the idea backwards. At each slot,
indexis the position of the digit in the sortedpool. The rank is the sum ofindex * fact[n - 1 - slot], plus 1. For"2314"the sum is 8, so the rank is 9.- When does the idea fail, and what do you do then?
It fails when the blocks at one slot have different sizes. In K-th Smallest in Lexicographical Order (LC 440) with
n = 13, the prefix 1 has 5 numbers and the prefix 2 has 1. Then you count the size of each block, and skip a block whilekis larger than its size.
SWE Reasoning
Spot it
- The problem asks for the
k-th item of a list in dictionary order, or for the rank of an item (Permutation Sequence (LC 60)). - The list is far too long to build, because
kcan reachn!. - All items that share the chosen prefix form a block, and every block at a slot has the same size.
- The answer is built one slot at a time, from an ordered
poolof unused choices.
The invariant, step by step
fact[m]holdsm!,poolholds the unused digits in order, andk -= 1turns the rank into the number of permutations before the answer.- At each slot,
block = fact[n - 1 - slot]is the size of one group of permutations that share the digits chosen so far. index = k // blockis the number of whole blocks before the answer. The digit atpool[index]starts the answer's block.k %= blockis the rank of the answer inside that block.pool.pop(index)removes the digit, so the next slot chooses from unused digits only, in order.- After
nslots,resultholds the digits of thek-th permutation, andkis 0.
Traps
- No
k -= 1. Everykthat is a multiple ofblockselects one block too far. Forn = 3, k = 3the result is"231"instead of"213". - Wrong block size.
fact[n - slot]is the size of the group one slot earlier. It raisesIndexErrorat slot 0. pool[index]instead ofpool.pop(index). The digit stays inpooland can be chosen again. The result forn = 3, k = 3becomes"211".- Blocks of different sizes. In K-th Smallest in Lexicographical Order (LC 440),
k // blockwith one fixed size picks the wrong block.