blog/org/taocp/20240415_permutations.org

Mixed-radix generation - TAOCP

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{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}

In this document, I try to implement this algorithm in 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);
}

0

0

0

0