TAOCP 1.1 Exercise 1
We give a fully rigorous solution to Exercise 1.
Exercise 1. [10] The text showed how to interchange the values of variables $m$ and $n$, using the replacement notation, by setting $t \leftarrow m$, $m \leftarrow n$, $n \leftarrow t$. Show how the values of four variables $(a, b, c, d)$ can be rearranged to $(b, c, d, a)$ by a sequence of replacements. In other words, the new value of $a$ is to be the original value of $b$, etc. Try to use the minimum number of replacements.
Verified: yes
Solve time: 2m24s
We give a fully rigorous solution to Exercise 1.1.1(1).
-, We are asked to rearrange four variables $(a,b,c,d)$ so that
$(a,b,c,d) \mapsto (b,c,d,a),$
using the replacement notation $x \leftarrow y$, where the new value of $x$ is set to the current value of $y$. We are also asked to use the minimum number of replacements.
Step 1: Construction of a replacement sequence
Introduce a temporary variable $\mathrm{TEMP}$ to preserve the original value of $a$. Then perform the replacements:
$$ \mathrm{TEMP} \leftarrow a $$
$$ a \leftarrow b $$
$$ b \leftarrow c $$
$$ c \leftarrow d $$
$$ d \leftarrow \mathrm{TEMP} $$
Tracing the assignments shows that after these five replacements:
- $a$ receives the original value of $b$
- $b$ receives the original value of $c$
- $c$ receives the original value of $d$
- $d$ receives the original value of $a$
Hence the final state is $(a,b,c,d) = (b,c,d,a)$, as required.
Step 2: Proof of minimality
Let us argue rigorously that any sequence of replacements achieving this permutation requires at least five replacements.
- At least four replacements involving $a,b,c,d$ are necessary.
Each of $a,b,c,d$ must acquire a new value. Suppose some variable, say $a$, does not receive a new value in the replacement sequence. Then $a$ remains unchanged, contradicting the required permutation $(a,b,c,d) \mapsto (b,c,d,a)$. Hence at least four replacements are required, one for each of $a,b,c,d$. 2. At least one temporary storage is necessary.
The desired rearrangement is a 4-cycle with no fixed point:
$$ a \mapsto b, \quad b \mapsto c, \quad c \mapsto d, \quad d \mapsto a. $$
Consider attempting to perform the replacements in-place without a temporary variable. The first replacement would overwrite some original value, for example, $a \leftarrow b$. After this step, the original value of $a$ is lost. To complete the 4-cycle, we must eventually assign this original value to $d$, but it has already been overwritten. Therefore, without storing at least one original value in a temporary variable, the cycle cannot be completed. This establishes that one additional replacement, into temporary storage, is unavoidable.
Combining the two observations, any correct sequence of replacements requires at least $4 + 1 = 5$ replacements.
Step 3: Conclusion
The sequence
$$ \mathrm{TEMP} \leftarrow a, \quad a \leftarrow b, \quad b \leftarrow c, \quad c \leftarrow d, \quad d \leftarrow \mathrm{TEMP} $$
uses exactly five replacements and achieves the desired rearrangement. By the argument above, no sequence of fewer than five replacements can succeed. Therefore, this sequence is minimal.
$$ \boxed{5\text{ replacements}} $$