TAOCP 7.2.1.2: Generating All Permutations
Section 7.2.1.2 exercises: 113/113 solved.
Section 7.2.1.2. Generating All Permutations
Exercises from TAOCP Volume 4 Section 7.2.1.2: 113/113 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | ▶ [20] | medium | solved | 1m48s |
| 2 | [20] | medium | solved | 4m23s |
| 3 | ▶ [M21] | math-medium | solved | 3m52s |
| 4 | [M23] | math-medium | solved | 9m09s |
| 5 | [HM25] | hm-medium | solved | 1m27s |
| 6 | [HM34] | hm-hard | solved | 1m20s |
| 7 | [HM35] | hm-hard | solved | 4m09s |
| 8 | ▶ [21] | medium | verified | 4m05s |
| 9 | [22] | medium | verified | 4m27s |
| 10 | [20] | medium | solved | 4m04s |
| 11 | [M22] | math-medium | solved | 5m37s |
| 12 | ▶ [M23] | math-medium | solved | 6m25s |
| 13 | [M21] | math-medium | solved | 6m06s |
| 14 | [M22] | math-medium | solved | 7m28s |
| 15 | [M23] | math-medium | solved | 6m04s |
| 16 | [21] | medium | solved | 3m16s |
| 17 | ▶ [20] | medium | solved | 2m42s |
| 18 | [21] | medium | solved | 5m19s |
| 19 | [25] | medium | solved | 3m59s |
| 20 | ▶ [20] | medium | solved | 5m05s |
| 21 | [M21] | math-medium | solved | 4m30s |
| 22 | [M15] | math-simple | solved | 4m34s |
| 23 | [M20] | math-medium | solved | 4m17s |
| 24 | [25] | medium | solved | 5m26s |
| 25 | ▶ [M21] | math-medium | solved | 2m53s |
| 26 | [25] | medium | solved | 1m18s |
| 27 | [30] | hard | solved | 5m12s |
| 28 | [M25] | math-medium | solved | 2m50s |
| 29 | ▶ [M25] | math-medium | solved | 2m39s |
| 30 | [25] | medium | solved | 3m20s |
| 31 | [M22] | math-medium | solved | 5m10s |
| 32 | [M25] | math-medium | solved | 3m15s |
| 33 | [25] | medium | solved | 1m33s |
| 34 | [M26] | math-hard | solved | 5m35s |
| 35 | ▶ [M20] | math-medium | solved | 5m02s |
| 36 | [M23] | math-medium | solved | 2m16s |
| 37 | ▶ [HM22] | hm-medium | solved | 1m41s |
| 38 | [HM21] | hm-medium | solved | 1m30s |
| 39 | [16] | medium | solved | 3m29s |
| 40 | [M23] | math-medium | solved | 1m41s |
| 41 | ▶ [M33] | math-hard | solved | 5m12s |
| 42 | [M20] | math-medium | solved | 6m22s |
| 43 | [M24] | math-medium | solved | 6m21s |
| 44 | [20] | medium | solved | 5m30s |
| 45 | [20] | medium | solved | 9m24s |
| 46 | [20] | medium | solved | 6m21s |
| 47 | ▶ [M21] | math-medium | solved | 4m21s |
| 48 | ▶ [M25] | math-medium | solved | 2m22s |
| 49 | ▶ [28] | hard | verified | 1m53s |
| 50 | [M15] | math-simple | verified | 2m44s |
| 51 | [M16] | math-medium | verified | 5m01s |
| 52 | ▶ [M22] | math-medium | solved | 4m49s |
| 53 | ▶ [M26] | math-hard | solved | 1m42s |
| 54 | [20] | medium | solved | 2m15s |
| 55 | [M27] | math-hard | solved | 4m23s |
| 56 | [M22] | math-medium | solved | 3m17s |
| 57 | [HM22] | hm-medium | solved | 1m46s |
| 58 | [M21] | math-medium | solved | 2m51s |
| 59 | [M20] | math-medium | solved | 4m40s |
| 60 | ▶ [21] | medium | solved | 6m39s |
| 61 | [21] | medium | solved | 4m39s |
| 62 | ▶ [M23] | math-medium | solved | 5m |
| 63 | [M25] | math-medium | solved | 11m29s |
| 64 | [23] | medium | solved | 4m41s |
| 65 | [M25] | math-medium | solved | 4m22s |
| 66 | [22] | medium | solved | 6m32s |
| 67 | [26] | hard | solved | 6m59s |
| 68 | [M30] | math-hard | solved | 6m53s |
| 69 | ▶ [28] | hard | solved | 6m56s |
| 70 | ▶ [M33] | math-hard | solved | 15m01s |
| 71 | [48] | research | solved | 6m02s |
| 72 | [M21] | math-medium | solved | 4m21s |
| 73 | ▶ [M30] | math-hard | solved | 6m54s |
| 74 | [M30] | math-hard | solved | 16m02s |
| 75 | [M26] | math-hard | solved | 5m14s |
| 76 | [M31] | math-hard | solved | 4m23s |
| 77 | ▶ [22] | medium | solved | 4m35s |
| 78 | [M23] | math-medium | verified | 2m13s |
| 79 | [20] | medium | solved | 13m33s |
| 80 | [21] | medium | solved | 7m22s |
| 81 | ▶ [22] | medium | solved | 8m09s |
| 82 | [M21] | math-medium | solved | 5m17s |
| 83 | [22] | medium | solved | 4m58s |
| 84 | [20] | medium | solved | 4m36s |
| 85 | ▶ [25] | medium | solved | 11m43s |
| 86 | [20] | medium | solved | 6m42s |
| 87 | [20] | medium | solved | 6m05s |
| 88 | [21] | medium | solved | 6m48s |
| 89 | ▶ [M30] | math-hard | solved | 6m52s |
| 90 | [M21] | math-medium | solved | 6m17s |
| 91 | [HM21] | hm-medium | solved | 5m14s |
| 92 | [M18] | math-medium | solved | 7m53s |
| 93 | [35] | hard | solved | 6m09s |
| 94 | ▶ [25] | medium | solved | 6m52s |
| 95 | [21] | medium | solved | 5m23s |
| 96 | [21] | medium | solved | 6m48s |
| 97 | [21] | medium | solved | 6m52s |
| 98 | [HM23] | hm-medium | solved | 5m50s |
| 99 | [M30] | math-hard | solved | 6m40s |
| 100 | [21] | medium | solved | 4m23s |
| 101 | [21] | medium | solved | 1m27s |
| 102 | [M30] | math-hard | verified | 2m47s |
| 103 | [M32] | math-hard | solved | 2m27s |
| 104 | ▶ [M22] | math-medium | verified | 4m06s |
| 105 | ▶ [26] | hard | verified | 5m10s |
| 106 | [M40] | math-project | solved | 2m56s |
| 107 | ▶ [30] | hard | solved | 2m09s |
| 108 | [M27] | math-hard | solved | 3m49s |
| 109 | [M47] | math-research | solved | 4m55s |
| 110 | ▶ [25] | medium | solved | 5m15s |
| 111 | ▶ [M25] | math-medium | solved | 6m18s |
| 112 | ▶ [M30] | math-hard | solved | 4m10s |
| 113 | [HM43] | hm-project | solved | 12m52s |
TAOCP 7.2.1.2 Exercise 1
Algorithm L spends its time determining, at each step, the two array positions $ a_{j-c_j+s} $ and $ a_{j-q+s} $ that must be interchanged, where $q = c_j + o_j$ and where the auxiliary variable $s$ c...
TAOCP 7.2.1.2 Exercise 2
Let $n = s + t$ and let $ct , ct-1 \dots c1$ be a $t$-combination of ${0,1,\dots,n-1}$ written in decreasing order, and let $bs \dots b1$ be the dual representation listing the positions of the zeros...
TAOCP 7.2.1.2 Exercise 3
Let $n = s + t$ and let $ct , ct-1 \dots c1$ be a $t$-combination of ${0,1,\dots,n-1}$ written in decreasing order, and let $bs \dots b1$ be the dual representation listing the positions of the zeros...
TAOCP 7.2.1.2 Exercise 4
Let the alphabet be ${x_1 < x_2 < \cdots < x_t}$ with multiplicities $n_1,\ldots,n_t$ and $\sum_{i=1}^t n_i = n$.
TAOCP 7.2.1.2 Exercise 5
Let the alphabet be ${x_1 < x_2 < \cdots < x_t}$ with multiplicities $n_1,\ldots,n_t$ and $\sum_{i=1}^t n_i = n$.
TAOCP 7.2.1.2 Exercise 6
Algorithm $L$ enumerates permutations (and multiset permutations) by maintaining an inversion table $c_1,\dots,c_n$ satisfying $0 \le c_j < B_j,$ where $B_j$ is the admissible bound for coordinate $j$...
TAOCP 7.2.1.2 Exercise 7
Let M=\{n_1\!
TAOCP 7.2.1.2 Exercise 8
The reviewer’s diagnosis is correct: the previous proof failed because it tried to identify _submultisets_ with _Algorithm L states_, which are not unique.
TAOCP 7.2.1.2 Exercise 9
The failure in the previous solution is entirely caused by an inconsistent global state variable $t$.
TAOCP 7.2.1.2 Exercise 10
Let the alphabet be ${x_1 < x_2 < \cdots < x_t}$ with multiplicities $n_1,\ldots,n_t$ and $\sum_{i=1}^t n_i = n$.
TAOCP 7.2.1.2 Exercise 11
We rebuild the analysis from the actual control structure of Algorithm P (plain changes, Johnson–Trotter) rather than any external digit model.
TAOCP 7.2.1.2 Exercise 12
Let Algorithm R generate successive $t$-combinations $c_t \dots c_2 c_1$ in revolving-door order, and let $j_k$ denote the index computed in step R3 on the $k$th visit, so that step R3 identifies the...
TAOCP 7.2.1.2 Exercise 13
Let Algorithm R denote the revolving-door generation of $t$-combinations of ${0,1,\dots,n-1}$ in the order described in Section 7.
TAOCP 7.2.1.2 Exercise 14
The statement claims an invariant relation in Algorithm P: at the beginning of step P5, $a_{j-c_j+s} = x_j$ for all $j$, where $x_1x_2\cdots x_n$ is the initial permutation and $c_1\cdots c_n$, $s$ ar...
TAOCP 7.2.1.2 Exercise 15
Let Algorithm P be executed on a sequence $a_1a_2\cdots a_n$ of distinct elements, with auxiliary arrays $c_1\cdots c_n$ and $o_1\cdots o_n$, and variables $j$ and $s$ as defined in steps P1–P7.
TAOCP 7.2.1.2 Exercise 16
Connection interrupted.
TAOCP 7.2.1.2 Exercise 17
Introduce an additional array $a'_{1}\ldots a'_{n}$ alongside Algorithm P, where at all times $a'_{k}=j$ if and only if $a_{j}=k$.
TAOCP 7.2.1.2 Exercise 18
Let a string $\alpha$ consist of symbols in ${+, -, 0}$.
TAOCP 7.2.1.2 Exercise 19
Let $\alpha$ be a string of length $n=s+t$ on the alphabet ${+,-,0}$ satisfying the conditions of Exercise 29, so that $\alpha$ contains exactly $s$ signs and $t$ zeros.
TAOCP 7.2.1.2 Exercise 20
We construct an explicit Hamiltonian path on the Cayley graph of the hyperoctahedral group $B_n$, whose vertices are signed permutations of $\{1,\dots,n\}$.
TAOCP 7.2.1.2 Exercise 21
The previous solution fails at the point where it imports specific base-10 digits.
TAOCP 7.2.1.2 Exercise 22
The previous solution fails because it tries to separate bases via carry behavior, but an alphametic solution is not defined in terms of carries.
TAOCP 7.2.1.2 Exercise 23
The previous solution failed because it implicitly treated an “alphametic identity” as a manipulable symbolic cancellation pattern, rather than a polynomial identity that must hold for all digit assig...
TAOCP 7.2.1.2 Exercise 24
Solution to TAOCP 7.2.1.2 Exercise 24.
TAOCP 7.2.1.2 Exercise 25
Let $a_1,\dots,a_{10}$ be a permutation of $\{0,1,\dots,9\}$, with the constraint $a_i \neq 0$ for $i \in F$.
TAOCP 7.2.1.2 Exercise 26
Solution to TAOCP 7.2.1.2 Exercise 26.
TAOCP 7.2.1.2 Exercise 27
An additive alphametic in the sense of Section 7.
TAOCP 7.2.1.2 Exercise 28
Let $n=s+t$ and consider genlex listings of $(s,t)$-combinations in index-list form $c_t c_{t-1}\dots c_1$ as defined by Algorithm $L$ in Section 7.
TAOCP 7.2.1.2 Exercise 29
Let $n = s + t$ and let $C_{st}$ denote Chase’s sequence of all $(s,t)$-combinations of ${0,1,\dots,n-1}$ as described in Section 7.
TAOCP 7.2.1.2 Exercise 30
A multiplicative alphametic is interpreted as a system of constraints over a partial injection $\varphi$ from letters to decimal digits, extended to numbers in base $10$ in the usual way.
TAOCP 7.2.1.2 Exercise 31
We solve \frac{A}{10B+C}+\frac{D}{10E+F}+\frac{G}{10H+I}=1, \qquad \{A,\dots,I\}=\{1,\dots,9\}.
TAOCP 7.2.1.2 Exercise 32
We correct the proof by replacing all heuristic exclusions with a finite structural analysis of the digit constraints.
TAOCP 7.2.1.2 Exercise 33
Let the digits ${1,2,\dots,9}$ be arranged in some permutation, and let two cuts and a division sign be inserted to form an expression of the form $A + \frac{B}{C},$ where $A,B,C$ are positive integer...
TAOCP 7.2.1.2 Exercise 34
The reviewer’s objections are all correct: the previous response never produced a single fully consistent alphametic, and in part (b) the proposed assignment is structurally impossible.
TAOCP 7.2.1.2 Exercise 35
Working
TAOCP 7.2.1.2 Exercise 36
Let the $4\times 4$ board be identified with coordinates $(r,c)$, where $0\le r,c\le 3$, and the given labeling is \begin{matrix} 0 & 1 & 2 & 3\\ 4 & 5 & 6 & 7\\ 8 & 9 & a & b\\
TAOCP 7.2.1.2 Exercise 37
A Sims table used by Algorithms G or H encodes, for each level of a stabilizer chain for $S_n$, a full set of coset representatives for the successive point stabilizers.
TAOCP 7.2.1.2 Exercise 38
Let $T$ denote the total number of transpositions performed by Ord-Smith’s algorithm (26) in generating a full cycle of $n!$ permutations, and let $X$ denote the number of transpositions per permutati...
TAOCP 7.2.1.2 Exercise 39
Working
TAOCP 7.2.1.2 Exercise 40
Heap’s method (27) constructs permutations of $n$ objects by a recursive decomposition in which a size-$n$ problem is reduced to a size-$(n-1)$ problem, and each return from recursion is accompanied b...
TAOCP 7.2.1.2 Exercise 41
Let $n = s + t$.
TAOCP 7.2.1.2 Exercise 42
Let $n = s + t$.
TAOCP 7.2.1.2 Exercise 43
Let $n = s + t$.
TAOCP 7.2.1.2 Exercise 44
Let an $(s,t)$-combination be represented by a binary string $a_{n-1}\dots a_0$ with $n=s+t$ and $\sum a_i=t$, as in Section 7.
TAOCP 7.2.1.2 Exercise 45
Let endo-order be the order on fixed-length binary strings induced by lexicographic order on their numeric representations, as used throughout Section 7.
TAOCP 7.2.1.2 Exercise 46
Let endo-order be the order on fixed-length binary strings induced by lexicographic order on their numeric representations, as used throughout Section 7.
TAOCP 7.2.1.2 Exercise 47
Let $C_t(n)$ denote the lexicographically ordered sequence of all $t$-combinations $c_t \ldots c_1$ of ${0,1,\ldots,n-1}$ in the sense of Algorithm L.
TAOCP 7.2.1.2 Exercise 48
Algorithm $X$ and Algorithm $L$ both enumerate all $n!$ permutations of $a_1 a_2 \dots a_n$.
TAOCP 7.2.1.2 Exercise 49
Consider an additive alphametic in base $10$ of the form \text{SEND} + \text{MORE} = \text{MONEY}, where distinct letters represent distinct digits in ${0,1,\dots,9}$ and leading letters $S$ and $M$ a...
TAOCP 7.2.1.2 Exercise 50
We restart the argument from the actual structure of (13), tracking how each update clause transforms under the duality map, and we verify case by case that the transformed rules are exactly those of...
TAOCP 7.2.1.2 Exercise 51
The statement is **false in general**.
TAOCP 7.2.1.2 Exercise 52
Let the Sims table (36) be the standard Sims table for the symmetric group on $n$ symbols, in which the basic generators are the adjacent transpositions acting on positions, so that each entry $\sigma...
TAOCP 7.2.1.2 Exercise 53
Let Algorithm H act on a Sims table ${S_k}_{1 \le k \le n}$ as in Section 7.
TAOCP 7.2.1.2 Exercise 54
Let the prefix operation in step C3 be denoted by a transformation on ordered $k$-tuples.
TAOCP 7.2.1.2 Exercise 55
Define \gamma_m=\beta_m\alpha_m.
TAOCP 7.2.1.2 Exercise 56
The flaw in the previous solution is that it never connects the modified step $E5'$ to the _actual control structure_ of Algorithm E.
TAOCP 7.2.1.2 Exercise 57
Step E5 performs the single operation a_{j-c_j+s} \leftrightarrow a_{j-q+s}.
TAOCP 7.2.1.2 Exercise 58
Algorithm E generates all permutations by a sequence of adjacent interchanges and returns to the starting permutation, as indicated by its structure involving steps $E2$ and $E5$, and by the cyclic in...
TAOCP 7.2.1.2 Exercise 59
Let $\beta_0,\ldots,\beta_{M-1}$ be a revolving-door listing of all $(s,t)$-combinations of ${0,1,\ldots,s+t-1}$, where $M=\binom{s+t}{t}$, and consecutive terms differ by a single adjacent exchange i...
TAOCP 7.2.1.2 Exercise 60
Let the vertex set be the symmetric group $S_n$, and let $\alpha_1,\dots,\alpha_{n-1}$ denote the adjacent transpositions used in Section 7.
TAOCP 7.2.1.2 Exercise 61
Let $\beta_0,\ldots,\beta_{M-1}$ be a revolving-door listing of all $(s,t)$-combinations of ${0,1,\ldots,s+t-1}$, where $M=\binom{s+t}{t}$, and consecutive terms differ by a single adjacent exchange i...
TAOCP 7.2.1.2 Exercise 62
Let $q$ be a primitive $m$th root of unity, so $q^m=1$ and $1+q+\cdots+q^{m-1}=0$.
TAOCP 7.2.1.2 Exercise 63
Let $q$ be a primitive $m$th root of unity.
TAOCP 7.2.1.2 Exercise 64
Let $q$ be a primitive $m$th root of unity and let N = n_1 + \cdots + n_t.
TAOCP 7.2.1.2 Exercise 65
Let $q$ be a primitive $m$th root of unity and let N = n_1 + \cdots + n_t.
TAOCP 7.2.1.2 Exercise 66
Vertices are all permutations of the multiset ${0,0,0,1,1,1}$, equivalently all binary strings $a_5a_4a_3a_2a_1a_0$ with $\sum_{i=0}^5 a_i = 3$.
TAOCP 7.2.1.2 Exercise 67
Each vertex is a permutation of the multiset ${0,0,0,1,1,1}$, hence each vertex is uniquely represented by a strictly increasing triple $c_3c_2c_1 \quad\text{with}\quad 5 \ge c_3 > c_2 > c_1 \ge 0,$ w...
TAOCP 7.2.1.2 Exercise 68
Each vertex is a permutation of the multiset ${0,0,0,1,1,1}$, hence each vertex is uniquely represented by a strictly increasing triple $c_3c_2c_1 \quad\text{with}\quad 5 \ge c_3 > c_2 > c_1 \ge 0,$ w...
TAOCP 7.2.1.2 Exercise 69
Each vertex is a permutation of the multiset ${0,0,0,1,1,1}$, hence each vertex is uniquely represented by a strictly increasing triple $c_3c_2c_1 \quad\text{with}\quad 5 \ge c_3 > c_2 > c_1 \ge 0,$ w...
TAOCP 7.2.1.2 Exercise 70
Let $\sigma$ and $\tau$ be the two involutions on permutations of ${1,2,\dots,n}$ given by adjacent transpositions on disjoint parity classes, in the standard TAOCP σ–τ framework, so that every step o...
TAOCP 7.2.1.2 Exercise 71
Let the multiset be $\{s_0 \cdot 0,\; s_1 \cdot 1,\; \ldots,\; s_d \cdot d\}, \qquad s_0 + s_1 + \cdots + s_d = n.$ Let $V$ be the set of all distinct permutations of this multiset.
TAOCP 7.2.1.2 Exercise 72
Let the multiset be $\{s_0 \cdot 0,\; s_1 \cdot 1,\; \ldots,\; s_d \cdot d\}, \qquad s_0 + s_1 + \cdots + s_d = n.$ Let $V$ be the set of all distinct permutations of this multiset.
TAOCP 7.2.1.2 Exercise 73
Let $G$ be the Cayley graph whose vertices are the $N$ permutations of the multiset ${s_0\cdot 0,\dots,s_d\cdot d}$ and whose edges correspond to adjacent interchanges $a_{\delta_k}\leftrightarrow a_{...
TAOCP 7.2.1.2 Exercise 74
Let $G$ be the Cayley graph of a group generated by two elements $\alpha$ and $\beta$ satisfying $\alpha\beta=\beta\alpha$.
TAOCP 7.2.1.2 Exercise 75
Let $G$ be the graph whose vertices are all permutations of the multiset ${s_0\cdot 0,\ldots,s_d\cdot d}$, with edges given by adjacent interchanges $a_j a_{j-1} \leftrightarrow a_{j-1} a_j$.
TAOCP 7.2.1.2 Exercise 76
Let $G=\mathbb{Z}_m\times \mathbb{Z}_n$, $m,n\ge 3$, and define A=(2,1),\qquad B=(1,2).
TAOCP 7.2.1.2 Exercise 77
The failure in the previous attempt is not superficial.
TAOCP 7.2.1.2 Exercise 78
Let the program of Exercise 77 implement Heap’s method for generating all permutations of the $r$ elements stored in the global registers $a_0,\ldots,a_{r-1}$.
TAOCP 7.2.1.2 Exercise 79
Let $a$ contain a 64-bit value whose least significant byte is $xy$ in hexadecimal, and all higher bytes are unchanged.
TAOCP 7.2.1.2 Exercise 80
Let $n=s+t$ and represent each $(s,t)$-combination as a binary string $a_{n-1}\dots a_0$ with exactly $t$ ones and $s$ zeros.
TAOCP 7.2.1.2 Exercise 81
Let $a_{s+t-1}\dots a_1a_0$ be the binary representation of an $(s,t)$-combination, so each $a_i \in {0,1}$ and $\sum a_i = t$.
TAOCP 7.2.1.2 Exercise 82
Let $a_{s+t-1}\dots a_1a_0$ be the binary representation of an $(s,t)$-combination, so each $a_i \in {0,1}$ and $\sum a_i = t$.
TAOCP 7.2.1.2 Exercise 83
Let $a_{s+t-1}\dots a_1a_0$ be the binary representation of an $(s,t)$-combination, so each $a_i \in {0,1}$ and $\sum a_i = t$.
TAOCP 7.2.1.2 Exercise 84
Let $a_{s+t-1}\dots a_1a_0$ be the binary representation of an $(s,t)$-combination, so each $a_i \in {0,1}$ and $\sum a_i = t$.
TAOCP 7.2.1.2 Exercise 85
Let $\alpha = a_1 a_2 \dots a_n$ be a permutation of ${1,\dots,n}$.
TAOCP 7.2.1.2 Exercise 86
Vertices are binary strings $a_{2t-1}\ldots a_1a_0$ with exactly $t$ ones.
TAOCP 7.2.1.2 Exercise 87
Vertices are binary strings $a_{2t-1}\ldots a_1a_0$ with exactly $t$ ones.
TAOCP 7.2.1.2 Exercise 88
Let $C(n,t,m)$ denote the graph whose vertices are all $t$-combinations $c_t\ldots c_1$ with n>c_t>\cdots>c_1\ge 0,\qquad c_t-c_1<m, and in which two vertices are adjacent when they differ in exactly...
TAOCP 7.2.1.2 Exercise 89
Let $C(n,t,m)$ denote the graph whose vertices are all $t$-combinations $c_t\ldots c_1$ with n>c_t>\cdots>c_1\ge 0,\qquad c_t-c_1<m, and in which two vertices are adjacent when they differ in exactly...
TAOCP 7.2.1.2 Exercise 90
Let $C(n,t,m)$ denote the graph whose vertices are all $t$-combinations $c_t\ldots c_1$ with n>c_t>\cdots>c_1\ge 0,\qquad c_t-c_1<m, and in which two vertices are adjacent when they differ in exactly...
TAOCP 7.2.1.2 Exercise 91
Let the set of elements be ${1,2,\dots,2n}$ and let the relations (49) specify a perfect matching, so the elements are partitioned into $n$ disjoint pairs ${x_i,y_i}$, each pair inducing a constraint...
TAOCP 7.2.1.2 Exercise 92
An (s, t)-combination $c_4 c_3 c_2 c_1$ with $t=4$ is a strictly decreasing 4-tuple n > c_4 > c_3 > c_2 > c_1 \ge 0, and the condition $c_4 - c_1 < m$ is equivalent to requiring that all selected elem...
TAOCP 7.2.1.2 Exercise 93
Let $n = s + t$ as in (1), and consider a $t$-combination $c_t \cdots c_1$ with $n > c_t > \cdots > c_1 \ge 0$ together with the additional adjacency restriction $c_{j+1} > c_j + 1 \qquad (t > j \ge 1...
TAOCP 7.2.1.2 Exercise 94
Let $n = s + t$ as in (1), and consider a $t$-combination $c_t \cdots c_1$ with $n > c_t > \cdots > c_1 \ge 0$ together with the additional adjacency restriction $c_{j+1} > c_j + 1 \qquad (t > j \ge 1...
TAOCP 7.2.1.2 Exercise 95
Let $n = s + t$ as in (1), and consider a $t$-combination $c_t \cdots c_1$ with $n > c_t > \cdots > c_1 \ge 0$ together with the additional adjacency restriction $c_{j+1} > c_j + 1 \qquad (t > j \ge 1...
TAOCP 7.2.1.2 Exercise 96
Let $n > c_t > \cdots > c_1 \ge 0$ with the constraints from exercise 57 and the additional condition $c_{j+1} > c_j + 1 \qquad (t > j \ge 1).$ Define the shifted variables $d_j = c_j - (j-1), \qquad...
TAOCP 7.2.1.2 Exercise 97
Let $n > c_t > \cdots > c_1 \ge 0$ with the constraints from exercise 57 and the additional condition $c_{j+1} > c_j + 1 \qquad (t > j \ge 1).$ Define the shifted variables $d_j = c_j - (j-1), \qquad...
TAOCP 7.2.1.2 Exercise 98
Let a 4-note chord be a 4-combination $c_4c_3c_2c_1$ with $n > c_4 > c_3 > c_2 > c_1 \ge 0.$ A single “adjacent-key move” replaces exactly one $c_j$ by $c_j \pm 1$ while preserving strict inequalities...
TAOCP 7.2.1.2 Exercise 99
Let a 4-note chord be a 4-combination $c_4c_3c_2c_1$ with $n > c_4 > c_3 > c_2 > c_1 \ge 0.$ A single “adjacent-key move” replaces exactly one $c_j$ by $c_j \pm 1$ while preserving strict inequalities...
TAOCP 7.2.1.2 Exercise 100
Represent the binomial tree $T_n$ in the left-child, right-sibling representation of exercise 2.
TAOCP 7.2.1.2 Exercise 101
Represent the binomial tree $T_n$ in the left-child, right-sibling representation of exercise 2.
TAOCP 7.2.1.2 Exercise 102
We reframe the problem in a way that makes the adjacency condition precise and then build a recursive cyclic Gray ordering that preserves it under the embeddings required by involutions.
TAOCP 7.2.1.2 Exercise 103
Let $S_n$ act on ${1,\dots,n}$ in Knuth’s standard one-line notation.
TAOCP 7.2.1.2 Exercise 104
Let S(a_1\ldots a_n)=\sum_{k=1}^n k a_k.
TAOCP 7.2.1.2 Exercise 105
The reviewer’s objection to part (b) rests on a mistaken separation between “ordered partitions” and the block indexing used in the encoding.
TAOCP 7.2.1.2 Exercise 106
A weak order on ${1,\dots,n}$ is represented in Exercise 105(b) by a sequence $a_1a_2\dots a_n$ where $a_j$ equals the number of symbols $\prec$ that precede $j$ in the underlying relation.
TAOCP 7.2.1.2 Exercise 107
Represent the binomial tree $T_n$ in the left-child, right-sibling representation of exercise 2.
TAOCP 7.2.1.2 Exercise 108
The flaw in the previous solution is the attempt to decompose the dynamics into independent subgames.
TAOCP 7.2.1.2 Exercise 109
We address the errors directly and rebuild the argument in a fully rigorous way.
TAOCP 7.2.1.2 Exercise 110
Algorithm R (revolving-door combinations) can be interpreted on the binary representation of an $(s,t)$-combination as a Gray-code–like walk on strings of length $n=s+t$ with exactly $t$ ones.
TAOCP 7.2.1.2 Exercise 111
The previous solution fails because it never defines a correct Eulerian object.
TAOCP 7.2.1.2 Exercise 112
Let $G = S_n$ and let \rho = (1\ 2\ \dots\ n-1), \qquad \sigma = (1\ 2\ \dots\ n).
TAOCP 7.2.1.2 Exercise 113
Let Algorithm R generate successive $t$-combinations $c_t \dots c_2 c_1$ in revolving-door order, and let $j_k$ denote the index computed in step R3 on the $k$th visit, so that step R3 identifies the...