TAOCP 7.2.1.1: Generating All n-Tuples
Section 7.2.1.1 exercises: 112/112 solved.
Section 7.2.1.1. Generating All n-Tuples
Exercises from TAOCP Volume 4 Section 7.2.1.1: 112/112 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [10] | simple | verified | 54s |
| 2 | [15] | simple | verified | 1m15s |
| 3 | ▶ [M20] | math-medium | verified | 2m44s |
| 4 | ▶ [18] | medium | verified | 1m04s |
| 5 | ▶ [22] | medium | verified | 1m41s |
| 6 | [M17] | math-medium | verified | 3m55s |
| 7 | [20] | medium | solved | 5m29s |
| 8 | [15] | simple | solved | 6m22s |
| 9 | [16] | medium | solved | 6m45s |
| 10 | ▶ [M21] | math-medium | solved | 6m10s |
| 11 | [M22] | math-medium | solved | 7m59s |
| 12 | ▶ [25] | medium | solved | 6m39s |
| 13 | [21] | medium | solved | 8m |
| 14 | [20] | medium | solved | 6m06s |
| 15 | ▶ [25] | medium | solved | 5m41s |
| 16 | [23] | medium | solved | 4m20s |
| 17 | [20] | medium | verified | 1m39s |
| 18 | ▶ [20] | medium | verified | 1m56s |
| 19 | [23] | medium | verified | 2m26s |
| 20 | [M36] | math-project | solved | 5m18s |
| 21 | [M30] | math-hard | solved | 2m39s |
| 22 | ▶ [22] | medium | verified | 3m04s |
| 23 | [20] | medium | verified | 1m48s |
| 24 | [M21] | math-medium | solved | 4m32s |
| 25 | ▶ [M25] | math-medium | solved | 2m01s |
| 26 | [25] | medium | solved | 6m39s |
| 27 | ▶ [20] | medium | solved | 6m25s |
| 28 | [M27] | math-hard | solved | 4m57s |
| 29 | [M24] | math-medium | solved | 5m46s |
| 30 | ▶ [M27] | math-hard | solved | 5m19s |
| 31 | [HM35] | hm-hard | solved | 6m28s |
| 32 | [M20] | math-medium | solved | 5m39s |
| 33 | ▶ [M20] | math-medium | solved | 6m22s |
| 34 | [M21] | math-medium | solved | 6m20s |
| 35 | [HM23] | hm-medium | solved | 5m |
| 36 | [21] | medium | solved | 6m54s |
| 37 | [HM23] | hm-medium | solved | 7m08s |
| 38 | ▶ [M25] | math-medium | solved | 6m05s |
| 39 | ▶ [HM30] | hm-hard | solved | 7m04s |
| 40 | ▶ [21] | medium | verified | 5m45s |
| 41 | [25] | medium | solved | 2m58s |
| 42 | [35] | hard | solved | 5m37s |
| 43 | [41] | project | solved | 4m |
| 44 | [M20] | math-medium | solved | 2m37s |
| 45 | [M40] | math-project | solved | 4m59s |
| 46 | [M23] | math-medium | solved | 4m52s |
| 47 | [HM24] | hm-medium | solved | 4m32s |
| 48 | [HM48] | hm-research | solved | 4m21s |
| 49 | [20] | medium | solved | 1m31s |
| 50 | ▶ [21] | medium | verified | 2m37s |
| 51 | [M24] | math-medium | solved | 3m26s |
| 52 | [M20] | math-medium | verified | 3m12s |
| 53 | [M46] | math-research | solved | 1m40s |
| 54 | [M20] | math-medium | solved | 4m14s |
| 55 | ▶ [35] | hard | solved | 2m36s |
| 56 | [M30] | math-hard | solved | 4m10s |
| 57 | [32] | hard | verified | 1m56s |
| 58 | ▶ [21] | medium | solved | 1m48s |
| 59 | [22] | medium | solved | 6m28s |
| 60 | [20] | medium | solved | 4m59s |
| 61 | [M30] | math-hard | solved | 4m14s |
| 62 | [46] | research | solved | 4m14s |
| 63 | [30] | hard | solved | 4m29s |
| 64 | ▶ [HM35] | hm-hard | solved | 5m13s |
| 65 | [30] | hard | solved | 4m13s |
| 66 | [40] | project | solved | 4m34s |
| 67 | [20] | medium | solved | 7m30s |
| 68 | [21] | medium | solved | 4m49s |
| 69 | ▶ [M25] | math-medium | solved | 4m46s |
| 70 | [21] | medium | solved | 5m46s |
| 71 | [M22] | math-medium | solved | 2m07s |
| 72 | [20] | medium | solved | 4m57s |
| 73 | ▶ [32] | hard | solved | 9m03s |
| 74 | [HM25] | hm-medium | solved | 6m13s |
| 75 | [32] | hard | solved | 6m27s |
| 76 | [M25] | math-medium | solved | 6m17s |
| 77 | [21] | medium | solved | 5m59s |
| 78 | [M26] | math-hard | solved | 6m25s |
| 79 | ▶ [M22] | math-medium | solved | 3m05s |
| 80 | [M20] | math-medium | verified | 1m46s |
| 81 | [M21] | math-medium | solved | 4m39s |
| 82 | ▶ [M25] | math-medium | solved | 5m55s |
| 83 | [41] | project | solved | 4m43s |
| 84 | ▶ [25] | medium | solved | 4m08s |
| 85 | ▶ [M25] | math-medium | solved | 4m07s |
| 86 | ▶ [26] | hard | solved | 8m42s |
| 87 | [27] | hard | solved | 5m11s |
| 88 | ▶ [25] | medium | solved | 4m17s |
| 89 | ▶ [25] | medium | solved | 5m33s |
| 90 | [26] | hard | solved | 4m31s |
| 91 | ▶ [34] | hard | solved | 3m05s |
| 92 | [M30] | math-hard | solved | 4m |
| 93 | ▶ [M28] | math-hard | solved | 5m03s |
| 94 | [22] | medium | verified | 1m42s |
| 95 | ▶ [M24] | math-medium | solved | 4m20s |
| 96 | ▶ [M28] | math-hard | solved | 1m47s |
| 97 | [M29] | math-hard | solved | 6m42s |
| 98 | [M34] | math-hard | solved | 5m19s |
| 99 | ▶ [M23] | math-medium | solved | 2m31s |
| 100 | [40] | project | solved | 8m03s |
| 101 | ▶ [M30] | math-hard | solved | 8m06s |
| 102 | [HM28] | hm-hard | verified | 1m18s |
| 103 | [M20] | math-medium | verified | 1m05s |
| 104 | [17] | medium | solved | 5m17s |
| 105 | [M31] | math-hard | solved | 7m49s |
| 106 | ▶ [M30] | math-hard | solved | 6m45s |
| 107 | [HM30] | hm-hard | solved | 6m21s |
| 108 | [M35] | math-hard | solved | 8m48s |
| 109 | [M22] | math-medium | solved | 5m24s |
| 110 | [M25] | math-medium | solved | 6m25s |
| 111 | [20] | medium | solved | 9m23s |
| 112 | ▶ [25] | medium | solved | 5m09s |
TAOCP 7.2.1.1 Exercise 1
Introduce shifted variables $b_j = a_j - l_j$.
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$.
TAOCP 7.2.1.1 Exercise 3
The flaw in the previous solution is not in the identification of trailing maximal components, but in how step M4 is counted inside a single transition.
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...
TAOCP 7.2.1.1 Exercise 5
Let $n$ be fixed and let each array location be indexed by an $n$-bit integer.
TAOCP 7.2.1.1 Exercise 6
We start from the binary representation of an integer $k$ with $n$ bits: k = (b_{n-1} b_{n-2} \dots b_0)_2,\quad b_j \in \{0,1\}, and we extend the notation by setting $b_n = 0$.
TAOCP 7.2.1.1 Exercise 7
Let $f = \text{COLOR}(x_1,\dots,x_n)$ be the Boolean function encoding proper 4-colorings of the US map, where each vertex variable $x_i$ takes values in ${0,1,2,3}$, represented in binary as in (73).
TAOCP 7.2.1.1 Exercise 8
Let $f = \text{COLOR}(x_1,\dots,x_n)$ be the Boolean function encoding proper 4-colorings of the US map, where each vertex variable $x_i$ takes values in ${0,1,2,3}$, represented in binary as in (73).
TAOCP 7.2.1.1 Exercise 9
The Chinese ring puzzle (Baguenaudier) has a standard representation as a binary state vector $(a_1,\dots,a_n)$ in which each $a_j \in {0,1}$ encodes whether ring $j$ is disengaged or engaged, and leg...
TAOCP 7.2.1.1 Exercise 10
The Chinese ring puzzle (Baguenaudier) has a standard representation as a binary state vector $(a_1,\dots,a_n)$ in which each $a_j \in {0,1}$ encodes whether ring $j$ is disengaged or engaged, and leg...
TAOCP 7.2.1.1 Exercise 11
Let $T_n$ denote the number of steps in the shortest procedure that removes all $n$ rings from the bar and then restores them, when the two smallest rings may be taken on or off simultaneously.
TAOCP 7.2.1.1 Exercise 12
No exercise statement is included after “Write the solution now.
TAOCP 7.2.1.1 Exercise 13
No exercise statement is included after “Write the solution now.
TAOCP 7.2.1.1 Exercise 14
No exercise statement is included after “Write the solution now.
TAOCP 7.2.1.1 Exercise 15
Consider the rooted ordered tree whose nodes are all strings $a_1 \dots a_j$ with $0 \le j \le n$ and $0 \le a_i < m_i$ for $1 \le i \le j$.
TAOCP 7.2.1.1 Exercise 16
Let $V={0,1,\dots,2n}$ be the node set, and let a binary $n$-tuple $(a_1,\dots,a_n)$ be represented by the directed cycle defined by the LINK fields 0 \to 1+n a_1 \to 2+n a_2 \to \cdots \to n+n a_n \t...
TAOCP 7.2.1.1 Exercise 17
Let $\Gamma_3 = g(0), g(1), \dots, g(7)$ denote the 3-bit Gray binary code from Section 7.
TAOCP 7.2.1.1 Exercise 18
Define a mapping $\varphi : {0,1,2,3} \to {0,1}^2$ by \varphi(0) = (0,0), \quad \varphi(1) = (0,1), \quad \varphi(2) = (1,1), \quad \varphi(3) = (1,0).
TAOCP 7.2.1.1 Exercise 19
Let $g(x)=x^3+2x^2+x-1$ in $\mathbb{Z}_4[x]$, so $-1\equiv 3 \pmod 4$, hence g(x)=x^3+2x^2+x+3.
TAOCP 7.2.1.1 Exercise 20
The earlier solution fails because it assumes structural facts about the octacode without grounding them in the construction from the previous exercise.
TAOCP 7.2.1.1 Exercise 21
Let $\alpha(n)$ denote the English name of $n$ written as a concatenation of capital letters, and interpret a pure alphametic as a bijection from letters to digits ${0,1,\dots,9}$ such that the corres...
TAOCP 7.2.1.1 Exercise 22
Each leaf of the given binary trie represents a right subcube, that is, a set of binary $n$-tuples obtained by fixing some coordinates along the root-to-leaf path and leaving the remaining coordinates...
TAOCP 7.2.1.1 Exercise 23
Let $g(k) = (\ldots a_2 a_1 a_0)_2$ and $k = (\ldots b_2 b_1 b_0)_2$, with the relation from (7), a_j = b_j \oplus b_{j+1}, \quad j \ge 0.
TAOCP 7.2.1.1 Exercise 24
The flaw in the previous solution is the attempt to treat an infinite XOR as a topological limit inside the product space.
TAOCP 7.2.1.1 Exercise 25
Let $g(k)=k\oplus \lfloor k/2\rfloor$, and write the binary expansions k=(\dots b_2 b_1 b_0)_2,\qquad g(k)=(\dots a_2 a_1 a_0)_2, with the standard Gray relations from (7.
TAOCP 7.2.1.1 Exercise 26
Let Algorithm E be the permutation generator defined in Section 7.
TAOCP 7.2.1.1 Exercise 27
Let $G$ be the Cayley graph of all permutations of ${1,\dots,n}$ generated by the three involutions \rho = (1\,2)(3\,4)(5\,6)\cdots,\quad \sigma = (2\,3)(4\,5)(6\,7)\cdots,\quad \tau = (3\,4)(5\,6)(7\...
TAOCP 7.2.1.1 Exercise 28
Let $G$ be the Cayley graph of all permutations of ${1,\dots,n}$ generated by the three involutions \rho = (1\,2)(3\,4)(5\,6)\cdots,\quad \sigma = (2\,3)(4\,5)(6\,7)\cdots,\quad \tau = (3\,4)(5\,6)(7\...
TAOCP 7.2.1.1 Exercise 29
Let $G$ be the Cayley graph of $S_n$ with generating set \{\sigma,\tau\}, \qquad \sigma = (1\,2\,\dots\,n), \quad \tau = (1\,2), where $n \ge 3$ is odd.
TAOCP 7.2.1.1 Exercise 30
Let $G$ be the Cayley graph of $S_n$ with generating set \{\sigma,\tau\}, \qquad \sigma = (1\,2\,\dots\,n), \quad \tau = (1\,2), where $n \ge 3$ is odd.
TAOCP 7.2.1.1 Exercise 31
Let $G$ be the Cayley graph of the symmetric group $S_n$ with generators $(\alpha_1,\dots,\alpha_k)$, and assume that each generator satisfies \alpha_j(x)=y for fixed distinct symbols $x,y \in {1,\dot...
TAOCP 7.2.1.1 Exercise 32
Let $x \in [0,1)$ and write its dyadic expansion x = 0.
TAOCP 7.2.1.1 Exercise 33
Let $x \in [0,1)$ and write its dyadic expansion x = 0.
TAOCP 7.2.1.1 Exercise 34
Let $x \in [0,1)$ and write its dyadic expansion x = 0.
TAOCP 7.2.1.1 Exercise 35
Let $x \in [0,1)$ and write its dyadic expansion x = 0.
TAOCP 7.2.1.1 Exercise 36
Let $X[0],X[1],\dots,X[n-1]$ be the array to be permuted, and let the inner loop in (42) denote the operation that is executed once per produced permutation, typically a visit or output of the current...
TAOCP 7.2.1.1 Exercise 37
Let $w_k(x)$ denote the $k$th Walsh function on $[0,1)$ in the Paley ordering, as defined in Section 7.
TAOCP 7.2.1.1 Exercise 38
Let $\omega = e^{2\pi i/3}$, so $\omega^3 = 1$ and $1 + \omega + \omega^2 = 0$.
TAOCP 7.2.1.1 Exercise 39
Let the 8 variables be indexed by $G={0,1}^3$, written $i=(i_1,i_2,i_3)$ with binary addition $i\oplus j$.
TAOCP 7.2.1.1 Exercise 40
The key correction is that the question is not about reconstructing the letters from the modified masks in some abstract sense, but about whether the _unchanged W2 procedure_ still functions correctly...
TAOCP 7.2.1.1 Exercise 41
The flaw in the previous solution is that it never connects the removed words to the actual image of the pairing construction in (23).
TAOCP 7.2.1.1 Exercise 42
The failure in the previous solution is not local but structural: it replaced Algorithm L’s actual auxiliary state with an unrelated DFS-stack model and then argued about bit changes in that invented...
TAOCP 7.2.1.1 Exercise 43
Let the 8 variables be indexed by $G={0,1}^3$, written $i=(i_1,i_2,i_3)$ with binary addition $i\oplus j$.
TAOCP 7.2.1.1 Exercise 44
Let the 8 variables be indexed by $G={0,1}^3$, written $i=(i_1,i_2,i_3)$ with binary addition $i\oplus j$.
TAOCP 7.2.1.1 Exercise 45
The previous argument failed because it treated the quotient construction in (b)–(d) as if it erased the combinatorial information carried by the internal perfect matchings.
TAOCP 7.2.1.1 Exercise 46
The previous attempt fails because it tries to “lift” a Gray cycle on $\{0,1\}^k$ into a block-selection rule without defining a consistent edge partition of the $(kr+2)$-cube.
TAOCP 7.2.1.1 Exercise 47
The previous solution fails because it introduces an external structure (perfect matchings) that is not part of the information supplied by Exercises 44 and 46.
TAOCP 7.2.1.1 Exercise 48
Let the 8 variables be indexed by $G={0,1}^3$, written $i=(i_1,i_2,i_3)$ with binary addition $i\oplus j$.
TAOCP 7.2.1.1 Exercise 49
Let the 8 variables be indexed by $G={0,1}^3$, written $i=(i_1,i_2,i_3)$ with binary addition $i\oplus j$.
TAOCP 7.2.1.1 Exercise 50
Let $Q_n(l)$ denote the graph on $\{0,1\}^n$ where two vertices are adjacent iff they differ in exactly $l$ coordinates.
TAOCP 7.2.1.1 Exercise 51
The flaw in the proposed argument is that it tries to transfer coordinate symmetry of the hypercube into symmetry of a _particular recursively defined cycle_, without proving that the recursion produc...
TAOCP 7.2.1.1 Exercise 52
The previous argument fails only because it does not properly justify two key facts: (i) the projection onto the first $j$ coordinates is indeed surjective, and (ii) how this surjectivity forces a low...
TAOCP 7.2.1.1 Exercise 53
Let $Q_n$ be the $n$-dimensional hypercube with vertex set ${0,1}^n$, where each edge is labeled by the coordinate in which its endpoints differ.
TAOCP 7.2.1.1 Exercise 54
Let the 8 variables be indexed by $G={0,1}^3$, written $i=(i_1,i_2,i_3)$ with binary addition $i\oplus j$.
TAOCP 7.2.1.1 Exercise 55
The bit string $(13)$ refers to the binary representation displayed in equation $(13)$ of the section, a_{23}\dots a_1 a_0 = 011001001000011111101101, which represents an $(s,t)$-combination with $s=1...
TAOCP 7.2.1.1 Exercise 56
The previous solution fails because it never produces a valid orbit enumeration.
TAOCP 7.2.1.1 Exercise 57
Let $Q_4$ denote the 4-dimensional hypercube graph whose vertex set is ${0,1}^4$ and whose edges connect vertices that differ in exactly one coordinate.
TAOCP 7.2.1.1 Exercise 58
Let $\alpha = (a_0, a_1, \dots, a_{2^n-1})$ be the delta sequence of an $n$-bit Gray cycle in the $n$-cube $Q_n$.
TAOCP 7.2.1.1 Exercise 59
Define the standard \(n\)-bit reflected Gray cycle \(C_n\) recursively as follows.
TAOCP 7.2.1.1 Exercise 60
The bit string $(13)$ refers to the binary representation displayed in equation $(13)$ of the section, a_{23}\dots a_1 a_0 = 011001001000011111101101, which represents an $(s,t)$-combination with $s=1...
TAOCP 7.2.1.1 Exercise 61
The bit string $(13)$ refers to the binary representation displayed in equation $(13)$ of the section, a_{23}\dots a_1 a_0 = 011001001000011111101101, which represents an $(s,t)$-combination with $s=1...
TAOCP 7.2.1.1 Exercise 62
Let $\Gamma_n$ be an $n$-bit Gray cycle in the sense of Section 7.
TAOCP 7.2.1.1 Exercise 63
Let $\Gamma_n = g(0), g(1), \dots, g(2^n-1)$ denote the $n$-bit Gray cycle as defined in (5)–(7).
TAOCP 7.2.1.1 Exercise 64
We restart from the actual structure of a Gray stream as a sequence of perfect matchings on the hypercube, and we avoid reducing the problem to an incorrect product or “state evolution” heuristic.
TAOCP 7.2.1.1 Exercise 65
Let $B_5$ denote the Beckett state graph: vertices are pairs $(S,Q)$ where $S\subseteq\{1,2,3,4,5\}$ and $Q$ is the FIFO queue of $S$.
TAOCP 7.2.1.1 Exercise 66
The previous solution failed for two independent reasons: a wrong state-space count and an imprecise formulation of what is actually being searched.
TAOCP 7.2.1.1 Exercise 67
Let $a_0, a_1, \ldots, a_{2^{n-1}-1}$ be the Gray binary code on $(n-1)$ bits from Section 7.
TAOCP 7.2.1.1 Exercise 68
Let $\Sigma_n = {0,1,2}^n$.
TAOCP 7.2.1.1 Exercise 69
The earlier solution fails because it assumes a matrix structure that is never derived from the definition.
TAOCP 7.2.1.1 Exercise 70
The previous solution failed because it replaced the problem with an unsupported structural claim.
TAOCP 7.2.1.1 Exercise 71
Connection interrupted.
TAOCP 7.2.1.1 Exercise 72
We are given a patient who may suffer from exactly one disease among $k$ candidates.
TAOCP 7.2.1.1 Exercise 73
We are given a patient who may suffer from exactly one disease among $k$ candidates.
TAOCP 7.2.1.1 Exercise 74
We are given a patient who may suffer from exactly one disease among $k$ candidates.
TAOCP 7.2.1.1 Exercise 75
We are given a patient who may suffer from exactly one disease among $k$ candidates.
TAOCP 7.2.1.1 Exercise 76
We are given a patient who may suffer from exactly one disease among $k$ candidates.
TAOCP 7.2.1.1 Exercise 77
We are given a patient who may suffer from exactly one disease among $k$ candidates.
TAOCP 7.2.1.1 Exercise 78
We are given a patient who may suffer from exactly one disease among $k$ candidates.
TAOCP 7.2.1.1 Exercise 79
We are given a patient who may suffer from exactly one disease among $k$ candidates.
TAOCP 7.2.1.1 Exercise 80
Let the given factorization be N = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}.
TAOCP 7.2.1.1 Exercise 81
Let $C$ denote the 2-digit $m$-ary modular Gray code cycle (a_0,b_0)\to(a_1,b_1)\to\cdots\to(a_{m^2-1},b_{m^2-1})\to(a_0,b_0), and let $C^\ast$ be its coordinate-swapped cycle
TAOCP 7.2.1.1 Exercise 82
The error in the proposed solution is fundamental: it tries to generate Hamilton cycles by modifying a single coordinate while keeping all others fixed.
TAOCP 7.2.1.1 Exercise 83
Represent each domino ${i,j}$, $0 \le i \le j \le 6$, as an undirected edge between vertices $i$ and $j$ in a multigraph $G$ on vertex set ${0,1,\dots,6}$, with one loop at each vertex $i$ correspondi...
TAOCP 7.2.1.1 Exercise 84
Represent each domino ${i,j}$, $0 \le i \le j \le 6$, as an undirected edge between vertices $i$ and $j$ in a multigraph $G$ on vertex set ${0,1,\dots,6}$, with one loop at each vertex $i$ correspondi...
TAOCP 7.2.1.1 Exercise 85
Represent each domino ${i,j}$, $0 \le i \le j \le 6$, as an undirected edge between vertices $i$ and $j$ in a multigraph $G$ on vertex set ${0,1,\dots,6}$, with one loop at each vertex $i$ correspondi...
TAOCP 7.2.1.1 Exercise 86
A Gray code on the set of all $n$-tuples $(a_1,\dots,a_n)$ of nonnegative integers is an infinite sequence in which every tuple appears exactly once and successive tuples differ in exactly one compone...
TAOCP 7.2.1.1 Exercise 87
The failure in the proposed solution is indeed not about coverage or monotone radius, but about an unjustified structural claim: one cannot appeal to a “standard Hamiltonian cycle on the shell” withou...
TAOCP 7.2.1.1 Exercise 88
We analyze Algorithm K as a generator of a cyclic Gray code on the $n$-cube, as constructed in Knuth’s treatment.
TAOCP 7.2.1.1 Exercise 89
Let $M(n)$ be the set of words over $\{\cdot,-\}$ with total weight $n$, where $\cdot$ has weight $1$ and $-$ has weight $2$.
TAOCP 7.2.1.1 Exercise 90
Let $[n]={1,2,\dots,n}$.
TAOCP 7.2.1.1 Exercise 91
Let $[n]={1,2,\dots,n}$ and let $\mathcal A$ be a family of $r$-subsets of $[n]$ such that for all $\alpha,\beta\in\mathcal A$ one has $\alpha\cap\beta\neq\varnothing$, with $r\le n/2$.
TAOCP 7.2.1.1 Exercise 92
Fix $n \ge 1$.
TAOCP 7.2.1.1 Exercise 93
We repair the proof by eliminating the false DFS assumptions and instead proving correctness directly from the recursive _edge-consumption structure_ of Algorithm R.
TAOCP 7.2.1.1 Exercise 94
For $m=5$ and $n=1$, the objects being cycled are single symbols from the alphabet ${0,1,2,3,4}$.
TAOCP 7.2.1.1 Exercise 95
Let $a_{n-1}\dots a_1a_0$ be a binary string with $\sum_{j=0}^{n-1} a_j=t$ and define $b_j=a_j\oplus a_{j-1}$ for $1\le j\le n-1$.
TAOCP 7.2.1.1 Exercise 96
We consider the recursive coroutine framework described in Section 7.
TAOCP 7.2.1.1 Exercise 97
We restart from the actual structure of Algorithms R and D in TAOCP §7.
TAOCP 7.2.1.1 Exercise 98
The central issue is that the previous solution never derived a usable recurrence for the prefix sum S_n(k)=\sum_{j=0}^{k-1} f_n(j), and instead _assumed_ it inherits the same recursive structure as $...
TAOCP 7.2.1.1 Exercise 99
Let $N = 2^n$ and let $f_n(0), f_n(1), \ldots, f_n(N-1)$ be the cycle from Exercise 97, viewed cyclically modulo $N$.
TAOCP 7.2.1.1 Exercise 100
Let $f_n(k)$ be the binary de Bruijn cycle of order $n$ constructed in Exercise 97, so that the infinite periodic sequence f_n(0), f_n(1), \ldots, f_n(2^n-1) contains every $n$-bit string exactly once...
TAOCP 7.2.1.1 Exercise 101
Let $S_n$ be the set of permutations of ${1,2,\dots,n}$.
TAOCP 7.2.1.1 Exercise 102
Let the alphabet have size $m$, totally ordered.
TAOCP 7.2.1.1 Exercise 103
Let $p$ be a prime.
TAOCP 7.2.1.1 Exercise 104
Let $S_n$ be the set of permutations of ${1,2,\dots,n}$.
TAOCP 7.2.1.1 Exercise 105
A string is written over a totally ordered infinite alphabet.
TAOCP 7.2.1.1 Exercise 106
A string is written over a totally ordered infinite alphabet.
TAOCP 7.2.1.1 Exercise 107
A string is written over a totally ordered infinite alphabet.
TAOCP 7.2.1.1 Exercise 108
Work over the alphabet ${0,1,\dots,9}$, interpreted as decimal digits, and use Knuth’s notion of m-ary primes and preprimes from Algorithm F in Section 7.
TAOCP 7.2.1.1 Exercise 109
Let $m=2^n$.
TAOCP 7.2.1.1 Exercise 110
Let $T_n$ denote the number of steps in the shortest procedure that removes all $n$ rings from the bar and then restores them, when the two smallest rings may be taken on or off simultaneously.