Iterating over integer strings with bounded entries and fixed sum

Question

Let $S = \{ 0, 1, \dots d\}^n$ be the set of strings (ordered tuples) with integer entries between $0$ and $d$. Consider the subset of strings $A \subset S$ whose entries sum to $k \cdot d$. Notationally, we can write this as $A = \{ s_1 s_2 \dots s_n \mid \sum_{i=1}^n s_i = k \cdot d, \text{ and }s_i \in \{0, \dots d\} \text{ for all } \ i=1,\dots n \}$.

I am looking for an algorithm that iterates over the strings in $A$. One might try to iterate over the strings in lexicographical order, starting with $\underbrace{d \ d \dots d}_{k \text{ times }} \ \underbrace{0 \ 0 \dots 0}_{n-k \text{ times }}$ and ending with $\underbrace{0 \ 0 \dots 0}_{n-k \text{ times }} \ \underbrace{d \ d \dots d}_{k \text{ times }}$.

For small values of $n$, $d$, and $k$, I have written down the iteration over $A$ in lexicographical order but I haven't been able to explicitly come up with an algorithm.

Answer 1

Let $L(n,d,t)$ be the lexicographically sorted list of strings of length $n$ with entries between $0$ and $d$ whose sum is $t$. You want $L(n,d,nk)$. This list can be computed recursively via $$ \begin{align} L(n,d,t)= &\quad((d)+\ell\mid \ell\in L(n-1,d,t-d)) \\&+((d-1)+\ell\mid \ell\in L(n-1,d,t-(d-1)) \\&+\vdots \\&+((1)+\ell\mid \ell\in L(n-1,d,t-1)) \\&+((0)+\ell\mid \ell\in L(n-1,d,t-0)) \end{align} $$ In other words, you recursively compute $L(n-1,d,t-d)$, then prepend the symbol $d$ to each list in that list. Then compute $L(n-1,d,t-(d-1))$, prepend the symbol $d$ to each list in that list, and concatenate the result to the previous list. And so on.

In pseudo-code:

def all_strings(n,d,t):
  if t = 0:
    yield the string of n zeroes, then stop iterating
  if t < 0 or n = 0:
    stop iterating
  for k in {d,d-1,...,1,0}:
    iterate though all_strings(n-1,d,t-k), prepending each with k

Edit: Even simpler. Given a string, $s$ here is how you find the next string in lexicographical order.

Every string $s$ can be uniquely written in the form $$s=t\mid x\mid 0^i\mid y\mid d^{j},$$ where $\mid$ is concatenation, $i,j\ge 0$,$x,y\in \{0,1,2\dots,d\}$, with $y\neq d$ and $x\neq 0$, and $t$ is a string. In words, $j$ is the number of $d$'s at the end of $s$, $y$ is the letter just before the $d$'s, $i$ the length of the block of zeroes just before $y$, and $x$ is the number before those zeroes, while $t$ is everything else.

Then the successor of $s$ is $$ s'=t\mid(x-1)\mid d^j\mid(y+1)\mid 0^i. $$