notes.html

problem 24 · 22 lines

<article>
<h3>Problem Analysis</h3>
<p>
    We are asked to find the one-millionth arrangement of the digits 0 through 9 when all such
    arrangements are listed in <a class="reference-source" href="https://en.wikipedia.org/wiki/Lexicographic_order" rel="noopener noreferrer" target="_blank">lexicographic order</a> - 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 <code>n</code> distinct symbols is <code>n!</code> (the <a class="reference-source" href="https://en.wikipedia.org/wiki/Factorial" rel="noopener noreferrer" target="_blank">factorial</a> of n). For ten digits that is 3,628,800 permutations, so generating a million of them is feasible but wasteful.
  </p>
<p>
    The key observation is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Factorial_number_system" rel="noopener noreferrer" target="_blank">factorial number system</a>: among all permutations sorted in <a class="reference-source" href="https://en.wikipedia.org/wiki/Lexicographic_order" rel="noopener noreferrer" target="_blank">lexicographic order</a>, exactly <code>(n-1)!</code> of them begin with each possible leading digit. Therefore, to find the permutation at rank <code>k</code> (counting from zero), I divide <code>k</code> by <code>(n-1)!</code>. 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 <a class="reference-source" href="https://en.wikipedia.org/wiki/Permutation#Numbering_permutations" rel="noopener noreferrer" target="_blank">unranking</a>. The complexity is <code>O(n^2)</code>: we make <code>n</code> digit selections, and each selection rebuilds the shrinking digit list in linear time. For <code>n = 10</code> this is trivially fast.
  </p>
<h3>Solution Approach</h3>
<h4>Factorial-Decomposition (Recursive Unranking) - Algorithm 0</h4>
<p>
    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.
  </p>
<p>
    Each call receives the sorted string of available digits and a 1-based target rank. I compute <code>fact = (len - 1)!</code>, then convert the rank to 0-based and divide: <code>current = (permutation_number - 1) / fact</code> gives the index of the digit to place here, and <code>remaining = (permutation_number - 1) % fact</code> gives the sub-rank. I remove <code>digits[current]</code> from the list and recurse on the smaller list with rank <code>remaining + 1</code> (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.
  </p>
<p>
    In Python, removing the chosen digit is a single clean slice expression, <code>digits[:current] + digits[current + 1:]</code>, and the <a class="reference-source" href="https://en.wikipedia.org/wiki/Factorial" rel="noopener noreferrer" target="_blank">factorial</a> comes from <code>math.factorial</code>. 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 <code>strcpy</code> of the sub-result. The C version implements its own <code>factorial</code> loop returning <code>long long</code>, which comfortably holds <code>9! = 362880</code>, and carefully frees both the intermediate digit buffer and the sub-result at each level to avoid leaks.
  </p>
</article>