TAOCP 7.2.1.1 Exercise 4
We construct a mixed-radix decrementing analogue of Algorithm M, operating in the same state space 0 \le a_j < m_j \quad (1 \le j \le n), but traversing it in reverse lexicographic order by repeatedly...
Section 7.2.1.1: Generating All n-Tuples
Exercise 4. ▶ [18] x 4. [18] On most computers it is faster to count down to 0 rather than up to m. Revise Algorithm M so that it visits all n-tuples in the opposite order, starting with (m1 −1, . . . , mn −1) and finishing with (0, . . . , 0).
Verified: yes
Solve time: 1m04s
Solution
We construct a mixed-radix decrementing analogue of Algorithm M, operating in the same state space
$$ 0 \le a_j < m_j \quad (1 \le j \le n), $$
but traversing it in reverse lexicographic order by repeatedly subtracting $1$ in the mixed-radix system.
Introduce a sentinel index $a_0$ only to terminate the borrow process in the same structural way as in Algorithm M.
Define the modified algorithm $M^\downarrow$ as follows.
Algorithm $M^\downarrow$ (Reverse mixed-radix generation).
M1. [Initialize.] Set $a_j \leftarrow m_j - 1$ for $1 \le j \le n$. Set $j \leftarrow n$.
M2. [Visit.] Visit the $n$-tuple $(a_1, \dots, a_n)$.
M3. [Prepare to subtract one.] Set $j \leftarrow n$.
M4. [Borrow if necessary.] If $a_j = 0$, set $a_j \leftarrow m_j - 1$, set $j \leftarrow j - 1$, and repeat step M4.
M5. [Decrease, unless done.] If $j = 0$, terminate the algorithm. Otherwise set $a_j \leftarrow a_j - 1$ and go to step M2.
Correctness follows from interpreting $(a_1, \dots, a_n)$ as a mixed-radix number
$$ A = \sum_{j=1}^n a_j \prod_{k=j+1}^n m_k, $$
so that step M5 performs $A \leftarrow A - 1$ whenever a borrow chain starting at position $j$ completes. Step M4 propagates a borrow exactly through consecutive zeros, replacing each $0$ by $m_j - 1$, which is the correct digit after subtraction in radix $m_j$. The process halts precisely when the tuple reaches $(0, \dots, 0)$, since in that case the borrow chain reaches $j=0$ and triggers termination.
Each execution of M5 corresponds to a single decrement of the mixed-radix integer $A$, so the algorithm visits every integer value from
$$ \prod_{j=1}^n (m_j - 1) $$
down to $0$ exactly once. Since the mapping between tuples and integers in the mixed-radix system is bijective, every admissible $n$-tuple appears exactly once, and the order is strictly decreasing in lexicographic sense.
This completes the proof. ∎