72 lines
2.0 KiB
Org Mode
72 lines
2.0 KiB
Org Mode
|
#+title: Mixed-radix generation - TAOCP
|
||
|
|
#+date: <2024-04-15 Mon>
|
||
|
|
#+category: taocp
|
||
|
|
#+pseudocode: true
|
||
|
|
#+bibliography: references.bib
|
||
|
|
#+slug: taocp/permutations
|
||
|
|
#+hugo_draft: true
|
||
|
|
|
||
|
|
#+hugo_front_matter_format: yaml
|
||
|
|
#+hugo_base_dir: ../../
|
||
|
|
#+hugo_custom_front_matter: :pseudocode true
|
||
|
|
|
||
|
|
In his draft on Generating all $n$ tuples, of The Art of Computer Programming, Knuth presents the following algorithm for the generation of $n$-tuples [cite:@knuthDraftSectionGenerating2002].
|
||
|
|
#+begin_export html
|
||
|
|
<pre id="hello-world-code" class="pseudocode">
|
||
|
|
\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}
|
||
|
|
</pre>
|
||
|
|
#+end_export
|
||
|
|
|
||
|
|
In this document, I try to implement this algorithm in C.
|
||
|
|
|
||
|
|
|
||
|
|
#+begin_src C
|
||
|
|
#include<stdio.h>
|
||
|
|
#include<stdlib.h>
|
||
|
|
|
||
|
|
void print_array(unsigned short int *a, size_t n) {
|
||
|
|
for (size_t i=0; i < n; i++) {
|
||
|
|
printf("%d", a[i]);
|
||
|
|
if (i < n - 1) {
|
||
|
|
printf(", ");
|
||
|
|
} else {
|
||
|
|
printf("\n");
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/** Apply function fun on the generated permutations
|
||
|
|
,*/
|
||
|
|
void mixed_radix(const size_t n, void (*fun)()) {
|
||
|
|
// Initialize
|
||
|
|
unsigned short int a[n];
|
||
|
|
unsigned short int m_0 = 2;
|
||
|
|
// Visit
|
||
|
|
fun(a);
|
||
|
|
// Prepare to add one
|
||
|
|
size_t j = n;
|
||
|
|
// Carry if necessary
|
||
|
|
if (a[j] == )
|
||
|
|
}
|
||
|
|
|
||
|
|
void main() {
|
||
|
|
const size_t n = 4;
|
||
|
|
unsigned short int a[n];
|
||
|
|
print_array(a, n);
|
||
|
|
}
|
||
|
|
#+end_src
|
||
|
|
|
||
|
|
#+RESULTS:
|
||
|
|
| 0 | 0 | 0 | 0 |
|
||
|
|
|
||
|
|
#+print_bibliography:
|