Problem Analysis
We are asked to find the one-millionth arrangement of the digits 0 through 9 when all such
arrangements are listed in lexicographic order - that is, dictionary order, where we compare element by element from left to right. A naive approach would generate all permutations in order and stop at the millionth, but the answer reveals a much more elegant structure. The total number of arrangements of n distinct symbols is n! (the factorial of n). For ten digits that is 3,628,800 permutations, so generating a million of them is feasible but wasteful.
The key observation is the factorial number system: among all permutations sorted in lexicographic order, exactly (n-1)! of them begin with each possible leading digit. Therefore, to find the permutation at rank k (counting from zero), I divide k by (n-1)!. The quotient tells me the index, into the sorted list of remaining digits, of the digit to place first; the remainder is the rank of the desired permutation among those sharing that leading digit. Removing the chosen digit leaves a strictly smaller, identically structured subproblem. This technique - converting a rank into its corresponding object directly - is called unranking. The complexity is O(n^2): we make n digit selections, and each selection rebuilds the shrinking digit list in linear time. For n = 10 this is trivially fast.
Solution Approach
Factorial-Decomposition (Recursive Unranking) - Algorithm 0
Both the Python and C implementations realise the same recursive algorithm, which mirrors the mathematical structure directly: at each level of recursion one digit is fixed and the remainder of the work is an identical, smaller problem. I chose recursion precisely because the subproblem after fixing a digit is the original problem in miniature.
Each call receives the sorted string of available digits and a 1-based target rank. I compute fact = (len - 1)!, then convert the rank to 0-based and divide: current = (permutation_number - 1) / fact gives the index of the digit to place here, and remaining = (permutation_number - 1) % fact gives the sub-rank. I remove digits[current] from the list and recurse on the smaller list with rank remaining + 1 (converting back to 1-based). The base case is a single remaining digit, which I return directly. The chosen digit is prepended to the result of the recursive call as the call stack unwinds.
In Python, removing the chosen digit is a single clean slice expression, digits[:current] + digits[current + 1:], and the factorial comes from math.factorial. In C, where strings are raw character buffers, I allocate a new array, copy every character except the chosen one, recurse, then build the result by writing the chosen character followed by a strcpy of the sub-result. The C version implements its own factorial loop returning long long, which comfortably holds 9! = 362880, and carefully frees both the intermediate digit buffer and the sub-result at each level to avoid leaks.