1.4 KiB
1.4 KiB
| title | author | date | draft | pseudocode | |
|---|---|---|---|---|---|
| Mixed-radix generation - |
|
2024-04-15T00:00:00+02:00 | true | true |
In its draft on Generating all \(n\) tuples, of The Art of Computer Programming, Knuth presents the following algorithm for the generation of $n$-tuples (Knuth 2002).
\begin{algorithm}
\caption{Mixed-radix generation}
\begin{algorithmic}
\State \textbf{M1.} [Initialize.] Set $a_j \gets 0$ for $0 \leq j \leq n$, and set $m_0 \gets 2$.
\State \textbf{M2.} [Visit.] Visit the \(n\)-tuple $(a_1, ..., a_n)$ (The program that wants to examine all $n$-tuples now does its thing.)
\State \textbf{M3.} [Prepare to add one.] Set $j \gets n$.
\State \textbf{M4.} [Carry if necessary.] If $a_j = m_j - 1$, set $a_j \gets 0$, $j \gets j - 1$ and repeat this step.
\State \textbf{M5.} [Increase, unless done.] If $j = 0$, terminate the algorithm. Otherwise set $a_j \gets a_j + 1$ and go back to step M2.
\end{algorithmic}
\end{algorithm}