# Algorithm for generating the next m-tuple of integers, subject to constraints

I am looking for an algorithm with the following characteristics:

• It is used to generate the set of integer vectors $\mathbf k=(k_1,\ldots,k_m)$, where $k_i\leq K_i$, $k_i\geq 0$, and $K_i$ are given positive integers. That is, I am looking for the cartesian product of the sets $\{1,\ldots,K_i\}$.
• Call $k=k_1+\ldots+k_m$. The output vectors are generated for increasing $k$. So first goes the vector with $k=0$, then the ones with $k=1$, then those for $k=2$, etc.
• The above is done without full enumeration or use of persistent data structures. That is, given the $i$-th generated vector, $\mathbf k_i$, the function should return a vector $\mathbf k_{i+1}$ that has not been generated before, if one exists.

It is fairly easy to generate the $\mathbf k$ vectors without the second requirement, but I am not sure how to handle that one.

• You might search for generation of restricted integer compositions. An equivalent formulation is generating $2\times m$ contingency tables, the counting of which is known to be a #$P$-hard problem. Sep 18 '15 at 20:19

Modulo an inessential detail, we are asked to generate mixed radix numbers with certain "digit" sums $k=k_1+\ldots+k_m$. In particular, given $\mathbf{k_i}$ satisfying the sum of components $k$, we are asked to find either the next larger representation having the same component sum, or if none exists, the smallest representation having component sum $k+1$, which we call $\mathbf{k_{i+1}}$.

Asking for the "next" $\mathbf{k_i}$ only makes sense if an ordering is imposed among solutions with a fixed component sum $k$. We will assume a lexicographic ascending order below, but a descending order would be as easy to arrange.

The basic idea is clear enough: find the rightmost (maximum) index $j$ such that we can increment $k_j$ by one and (in compensation) decrease by one the sum of components with index greater than $j$ in the way that represents the smallest possible ($m-j$ component) mixed radix number (with the specified component sum).

The "boundary" case where no such index $j$ is possible, so that we increment $k$ and start over with the smallest possible mixed radix number with component sum $k+1$, is essentially the same as the latter subproblem of the typical step. It therefore bears discussing how to find the smallest number with a given sum $k$ of entries.

Fortunately this subproblem has an easy solution: we choose digits from right to left in a greedy fashion, as large as possible subject to the constrained sum $k$.

This is good point to pin down the inessential detail mentioned at the outset. The Question poses a sum of components $k_i \in \{1,\ldots,K_i\}$ (although confusingly, the condition $k_i \ge 0$ is also stated). If the components are all required to meet $k_i \ge 1$ (or for that matter any other nonzero lower bounds, possibly determined by the index $i$), we cannot achieve any sum of components less than $m$ (seeing as there are $m$ components to be added).

Therefore it is convenient to subtract one from each component, choosing instead that $k_i \in \{0,\ldots,K_i-1\}$, which makes the analogy with mixed radix representations more explicit. Correspondingly, the digit sums can then progress from $\sum_{i=1}^m k_i = 0$ to $\sum_{i=1}^m (K_i - 1)$.

Least representation of rightmost $m-j$ digits having component sum $c$

Set $\ell = m$.

While $\ell > j$:

• Set $k_\ell = \max \{c, K_\ell - 1 \}$.
• Set $c = c - k_\ell$.
• Set $\ell = \ell - 1$.

Return success if $c = 0$, otherwise fail.

Find rightmost index $j$ such that $k_j$ can be incremented

Scan from right to left to find an index $j \gt 1$ such that $k_j \gt 0$.

If no such index exists, fail.

Do:

• Set $j = j-1$.

Until $k_j \lt K_j - 1$.

For efficiency we can keep a running sum $c$ of entries above index $j$, since we will offset the increment of $k_j$ by decrementing the sum $c$ of components beyond that point.

• Thanks a lot for the helpful response! Indeed I should have written ${0,\ldots,K_i-1}$. Sep 19 '15 at 7:56