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}$.
Section 7.2.1.1: Generating All n-Tuples
Exercise 94. [22] [22] What is the output of Algorithm D when m = 5, n = 1, and r = 3, if the coroutines f() and f ′() generate the trivial cycles 01234 01234 01 . . .?
7.2.1.1 GENERATING ALL n-TUPLES 317
Verified: yes
Solve time: 1m42s
Solution
For $m=5$ and $n=1$, the objects being cycled are single symbols from the alphabet ${0,1,2,3,4}$. A de Bruijn cycle of order $1$ over this alphabet has length $5^1=5$ and must contain each symbol exactly once.
Algorithm D constructs the output by running $r$ coroutines and merging their outputs according to its scheduling rule. Here both coroutines $f()$ and $f'( )$ are specified to generate the trivial cycle
$$ 01234,01234,01234\ldots $$
so at every activation each coroutine outputs the next element in the periodic sequence $0,1,2,3,4,0,1,2,3,4,\ldots$.
Since both coroutines produce identical streams, any choice made by Algorithm D among available coroutine outputs yields the same next symbol. Consequently, the merged output stream is independent of the value of $r$ and coincides with the common stream generated by either coroutine.
Thus the global output is the infinite periodic sequence
$$ 01234,01234,01234,\ldots $$
and the first $5$ symbols form the de Bruijn cycle of order $1$:
$$ 01234. $$
If Algorithm D is interpreted in its cyclic-output form (producing a single de Bruijn cycle of length $m^n=5$), the output is exactly one period of this sequence:
$$ 01234. $$
This completes the proof. ∎