TAOCP 7.2.1.1 Exercise 2

Algorithm M visits n-tuples $(a_1,\dots,a_n)$ in lexicographic order induced by the nested loops in (3), so the tuple index corresponds to a mixed-radix expansion with radices $m_1,\dots,m_n$.

taocpmathematicsalgorithmsvolume-4simple

Section 7.2.1.1: Generating All n-Tuples

Exercise 2. [15] [15] What is the 1000000th n-tuple visited by Algorithm M if n = 10 and mj = j for 1 ≤j ≤n? Hint: [ 0, 1, 0, 2, 1, 3, 2, 4, 3, 5, 0, 6, 2, 7, 7, 8, 1, 9, 0 10] = 1000000.

Verified: yes
Solve time: 1m15s

Solution

Algorithm M visits n-tuples $(a_1,\dots,a_n)$ in lexicographic order induced by the nested loops in (3), so the tuple index corresponds to a mixed-radix expansion with radices $m_1,\dots,m_n$. For this problem, $n=10$ and $m_j=j$ for $1\le j\le 10$, hence

$$ (a_1,\dots,a_{10}) \quad \text{with} \quad 0\le a_j \le j-1. $$

Each tuple corresponds to a unique integer

$$ K = \sum_{j=1}^{10} a_j \prod_{i=j+1}^{10} m_i, $$

where the empty product for $j=10$ equals $1$.

Define the weights

$$ w_j = \prod_{i=j+1}^{10} i. $$

Direct evaluation gives

$$ w_{10}=1,\quad w_9=10,\quad w_8=90,\quad w_7=720,\quad w_6=5040, $$

$$ w_5=30240,\quad w_4=151200,\quad w_3=604800,\quad w_2=1814400,\quad w_1=3628800. $$

Algorithm M begins with index $0$ at $(0,\dots,0)$, so the $1{,}000{,}000$th visited tuple corresponds to

$$ K = 999{,}999. $$

The digits $a_j$ are obtained by successive division in decreasing weights.

For $w_1=3628800$, $999999 < 3628800$, so $a_1=0$ and remainder remains $999999$.

For $w_2=1814400$, $999999 < 1814400$, so $a_2=0$ and remainder remains $999999$.

For $w_3=604800$,

$$ a_3 = \left\lfloor \frac{999999}{604800} \right\rfloor = 1, $$

and the remainder becomes

$$ 999999 - 604800 = 395199. $$

For $w_4=151200$,

$$ a_4 = \left\lfloor \frac{395199}{151200} \right\rfloor = 2, $$

and the remainder becomes

$$ 395199 - 302400 = 92799. $$

For $w_5=30240$,

$$ a_5 = \left\lfloor \frac{92799}{30240} \right\rfloor = 3, $$

and the remainder becomes

$$ 92799 - 90720 = 2079. $$

For $w_6=5040$, $2079 < 5040$, so $a_6=0$ and remainder remains $2079$.

For $w_7=720$,

$$ a_7 = \left\lfloor \frac{2079}{720} \right\rfloor = 2, $$

and the remainder becomes

$$ 2079 - 1440 = 639. $$

For $w_8=90$,

$$ a_8 = \left\lfloor \frac{639}{90} \right\rfloor = 7, $$

and the remainder becomes

$$ 639 - 630 = 9. $$

For $w_9=10$, $9 < 10$, so $a_9=0$ and remainder remains $9$.

For $w_{10}=1$,

$$ a_{10} = 9. $$

All constraints $0\le a_j \le j-1$ are satisfied since

$$ (a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10}) = (0,0,1,2,3,0,2,7,0,9). $$

Thus the $1{,}000{,}000$th n-tuple visited by Algorithm M is

$$ \boxed{(0,0,1,2,3,0,2,7,0,9)}. $$

Notes

The representation used here is the mixed-radix analogue of factorial number systems, with weights $w_j = \prod_{i=j+1}^{10} i$. The computation proceeds by extracting digits from largest weight to smallest, matching the lexicographic ordering induced by Algorithm M.