Detailed mathematical approach

Problem Summary

The problem asks for the millionth permutation of the digits \(0,1,2,\dots,9\) when all \(10!\) permutations are listed in lexicographic order. More generally, given any ordered set of \(n\) distinct symbols and a 1-based index \(k\), we want the \(k\)-th lexicographic permutation.

Generating every permutation up to the target would be wasteful, because \(10!=3{,}628{,}800\). The key fact is that lexicographic order is organized into factorial-sized blocks, so the desired permutation can be addressed directly from its rank.

Mathematical Approach

Let the available symbols be \(A=\{a_0<a_1<\cdots<a_{n-1}\}\), and let \(r=k-1\) be the 0-based rank. The entire method is a repeated answer to one question: which block of size \((m-1)!\) contains the target permutation when \(m\) symbols remain?

Factorial-Sized Lexicographic Blocks

Fix the first symbol of a permutation of \(m\) distinct symbols. The remaining \(m-1\) symbols can then be arranged in exactly \((m-1)!\) ways. Therefore the lexicographic list splits into consecutive blocks of size \((m-1)!\), one block for each possible first symbol in sorted order.

If the current 0-based rank is \(r\), then the correct block number is

$q=\left\lfloor \frac{r}{(m-1)!} \right\rfloor,$

so the next symbol is the \(q\)-th smallest unused symbol. After choosing it, the rank inside that block becomes

$r'=r\bmod (m-1)!.$

A Recursive Rank-to-Permutation Rule

This gives a clean recurrence. If \(T(A,r)\) denotes the permutation of rank \(r\) among the symbols in \(A\), and if \(A=\{a_0<\cdots<a_{m-1}\}\), then with \(q=\lfloor r/(m-1)!\rfloor\) and \(r'=r\bmod (m-1)!\),

$T(A,r)=a_q\text{ followed by }T(A\setminus\{a_q\},r').$

The base case is \(T(\{a\},0)=a\). The invariant is simple and crucial: after fixing a prefix, the updated rank is always the lexicographic rank of the remaining suffix among the remaining unused symbols.

Factoradic and Lehmer Code Interpretation

The same procedure can be written as a factorial-number-system expansion:

$r=c_{n-1}(n-1)!+c_{n-2}(n-2)!+\cdots+c_1 1!+c_0 0!,$

with \(0\le c_i\le i\). These coefficients are unique. At step \(i\), the coefficient \(c_i\) tells us which remaining symbol to take from the sorted pool. In permutation language, \((c_{n-1},c_{n-2},\dots,c_0)\) is the Lehmer code of the answer.

This viewpoint explains why no backtracking is needed: each quotient fixes one position permanently, and each remainder passes the unresolved part of the problem to the next smaller factorial scale.

Worked Example: The Millionth Permutation

For the original problem we convert from 1-based to 0-based rank:

$r=1{,}000{,}000-1=999{,}999.$

Its factoradic expansion is

$999{,}999=2\cdot 9!+6\cdot 8!+6\cdot 7!+2\cdot 6!+5\cdot 5!+1\cdot 4!+2\cdot 3!+1\cdot 2!+1\cdot 1!+0\cdot 0!.$

So we choose, in order, the \(2\)-nd, \(6\)-th, \(6\)-th, \(2\)-nd, \(5\)-th, \(1\)-st, \(2\)-nd, \(1\)-st, \(1\)-st, and \(0\)-th remaining digits. Starting from \([0,1,2,3,4,5,6,7,8,9]\), those choices produce

$2,\ 7,\ 8,\ 3,\ 9,\ 1,\ 5,\ 4,\ 6,\ 0,$

hence the millionth lexicographic permutation is

$2783915460.$

How the Code Works

The C++, Python, and Java implementations accept a symbol string and a 1-based permutation index, then sort the symbols so that lexicographic order is defined unambiguously. They compute \(n!\) for the symbol count and reject any request outside the valid range \(1\le k\le n!\).

After that, the implementation converts \(k\) to the 0-based rank \(r=k-1\), stores the remaining symbols in a mutable ordered pool, and repeats the quotient-remainder step. At each round it divides by \((m-1)!\), uses the quotient as an index into the pool, appends the chosen symbol to the answer, removes it from the pool, and continues with the remainder.

The implementations also include small checkpoints such as the first and last permutations of the symbols \(0,1,2\), which verify that the ordering and the off-by-one convention are correct before solving the main case.

Complexity Analysis

There are \(n\) selection rounds. In these implementations the remaining symbols are kept in a simple list or array-like structure, so removing the chosen symbol costs \(O(n)\) in the worst case. The total running time is therefore \(O(n^2)\), and the extra space is \(O(n)\).

For the original input \(n=10\), this cost is tiny. The important gain is conceptual: the algorithm computes one target permutation directly instead of enumerating all \(10!\) permutations that come before it.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=24
2. Factorial number system: https://en.wikipedia.org/wiki/Factorial_number_system
3. Lehmer code: https://en.wikipedia.org/wiki/Lehmer_code
4. Lexicographical order: https://en.wikipedia.org/wiki/Lexicographical_order
5. Permutation: https://en.wikipedia.org/wiki/Permutation