1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – hardmath Sep 18 '15 at 20:19
1
$\begingroup$

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.

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

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.