Jump straight to the kth ordering
Find the kth ordering of the numbers 1 to n in dictionary order without listing the ones before it, by counting how many orderings start with each choice. About 16 minutes.
Blocks of equal size
List the orderings of 1, 2, 3 in dictionary order: 123, 132, 213, 231, 312, 321. Those starting with 1 come first, then those starting with 2, then 3. Each block has the same size: two, which is 2 factorial.
For n digits, each block has (n − 1) factorial orderings. So to find the kth ordering, work out which block it is in.
fact = [1, 1, 2, 6] block = fact[2] # 2 per first digit idx = 3 // block # 1
k is 3, so position 2. Block size 2: position 2 divided by 2 is 1, so the second digit, 2, goes first.
Repeat on what is left
The block number says which of the remaining digits goes first. Take it out of the list of digits and add it to the answer. The position of the wanted ordering inside its block is the remainder of the division.
Now repeat with one fewer digit, using the remainder as the new k. Counting from 0 matters: subtract 1 from k at the start, so that the first ordering has position 0.
k = k % block digits.pop(idx)
n is 4. How many orderings start with the digit 1?
- A6, which is 3 factorial
- B4
- C24
Show the answer
6, which is 3 factorial. The remaining three digits can be ordered in 3 factorial ways.
Permutation sequence
The numbers 1 to n have n! orderings. Listed in dictionary order (as digit strings), the orderings of 1, 2, 3 are "123", "132", "213", "231", "312" and "321". Given n and k, return the kth ordering in this list, counting from k = 1, as a string of digits.
n = 3, k = 3 → "213"
1 ≤ n ≤ 9 · 1 ≤ k ≤ n!