0
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Mar 20, 2019 at 12:40
  • $\begingroup$ @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). $\endgroup$ Mar 20, 2019 at 16:05
  • $\begingroup$ @ChrisHarshaw Actually see edit for an even simpler method, which works similarly to Gosper's hack. $\endgroup$ Mar 20, 2019 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.