Enumerating m-tuples of Integers Subject to Implication Constraints [closed]

Question

How do I enumerate all $m$-tuples of positive integers $(a_1,...,a_m)$ subject to the following constraints?

1. For each $i$ in $\{ 1,\ldots,m \}$, there is a number $n_i \geq 0$ such that $a_i \leq n_i$.

2. For each ordered pair $(i,j)$ with $i,j$ in $\{ 1,\ldots ,m \}$, there are numbers $c_{ij}, d_{ij} \geq 0$ such that: $$ \mbox{if $a_i > c_{ij}$, then $a_j \leq d_{ij}$.} $$

3. $c_{ij} = c_{ji}$.

So far, I have come up with the following solution. Is there a more efficient way to do this?

for a[1]=0,...,n[1] do 
{
    for j=2,...,m do
    {
        if a[1] > c[1][j] then n[j]:=min{n[j],d[1][j]}
                          else n[j]:=n[j]
    }
    for a[2]=0,...,n[2] do 
    {
        for j=3,...,m do
        {
            if a[2] > c[2][j] then n[j]:=min{n[j],d[2][j]}
                              else n[j]:=n[j]
        }
        for a[3]=0,...,n[3] do
        {
            .
            .
            .
            for a[m]=0,...,n[m] do
            {
                print (a[1],...,a[m])
            }
        }...}}

Answer 1

This isn't research mathematics, but since there is an answer already I'll add one. The key issue for efficiency in this type of problem is to not generate partial potential solutions that are not partial real solutions. I.e., no dead ends in the search. The overall structure you have (ignoring the question of how to encode it properly on a computer) is correct except that you need to use the conditional constraints backwards too. The rule "if $a_i\gt c_{ij}$ then $a_j\le d_{ij}$" implies the contrapositive "if $a_j\gt d_{ij}$ then $a_i\le c_{ij}$". If you use that as well when computing an upper bound for the next element (or you prove that it won't ever make a difference in your case), then every partial solution is a real solution when extended by zeros. So the overall running time will be a small multiple of the number of solutions. I don't think you can do better in general, but there is room for optimizing the computation of the upper bounds by avoiding calculations you already did last time you visited that place.

Answer 2

Unless m is small, some of the cij are small, or a lot of the dij are small, ( or you know something else which tells you the resulting list is small), you aren't going to save a lot by recoding.

At the moment, you have N many possible tuples where N is the product of m integers. Until I know more, I will say N "looks like" n^m. You know minimal values you need to check: say c_i is the mimimum over j of the cij, and C is the product of the c_i. N/C might be big enough to motivate you, but to me it looks just like (n/c)^m, and since you have to do C many tuples already, and extra cycles to decide about the rest, you may find that simple and right is better than complex and buggy. It's your call.

If the dij are such that, once outside the C-many unconstrained examples, they are close enough to the cij that you expect to toss most of the N-C possibilities away, then you want to organize the constraints so that the small loops are on the outside, and that you fail and toss a partial tuple sooner. The idea (which if you look at constraint programming literature) is that the tighter constraints narrow the search space, and you waste less time on failure. Thus you might see where dij-cij is smallest once you head outside C.

Your brief description in the comments does not give me much guidance. If you want more practical suggestions, some estimates of all the parameters (m, ns,cs,ds) as well as good guesses on C, N, and the expected size of the output would help give me such guidance.

My advice would be different if the tuples lay in a hyperplane sandwich ( e.g. sum of coordinates lie in a small range of numbers). Efficient enumeration would be harder but worthwhile, especially if you can memoize certain computations.

Gerhard "Or Try A Constraint Solver" Paseman, 2015.11.09