Iterating over integer strings with bounded entries and fixed sum

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.

• Why not simplest backtrack algorithm? Mar 18, 2019 at 23:01
• thanks for the comment, @Vladislav. Can you describe more precisely what you mean? Perhaps in the form of an answer is best too. Mar 19, 2019 at 3:20
• For $d=1$ there's Gosper's hack. Mar 19, 2019 at 11:52

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.$$

• Nice observation that you can iterate over the set of strings $A$ recursively! Do you know of a way to change the recursive iterator into a non-recursive one by somehow unrolling the recursion? Mar 20, 2019 at 12:40
• @ChrisHarshaw Yes. Maintain a stack of partial strings. Over and over, pop a string s from the stack, and push on s with all possible characters appended to s. When the sum of s is equal to kd, then yield s padded with zeroes (or whatever the non python equivalent of yield is). Mar 20, 2019 at 16:05
• @ChrisHarshaw Actually see edit for an even simpler method, which works similarly to Gosper's hack. Mar 20, 2019 at 23:43