Enumerating m-tuples of Integers Subject to Implication Constraints

Question

How do I enumerate all m-tuples of nonnegative integers (a[1],...,a[m]) subject to the following constraints?

1. For each i in {1,...,m}, there is a number n[i] >= 0 such that a[i] <= n[i].

2. For each ordered pair (i,j) with i,j in {1,...,m}, there are numbers c[i][j], d[i][j] >= 0 such that:

   if a[i] > c[i][j], then a[j] <= d[i][j].

3. c[i][j] = c[j][i].

So far, I have come up with the following solution. Is there a more efficient way to do this? I am programming in C or C++.

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])
            }
        }...}}

I see one major inefficiency in this algorithm. To see it, take m=2 for simplicity. Say n[1] = n[2] = 2 and c[i][j] = d[i][j] = 0 for all i,j. Now let's go through the algorithm.

Start at a[1] = 0: n[2] is unchanged because a[1] <= 0. We print (0,0),(0,1),(0,2).

Next is a[1] = 1: Since a[1] > c[1][2], n[2] is changed in the loop to min{ n[2],d[1][j] } = 0. We print (1,0).

Finally a[1] = 2: Since a[1] > c[1][2], n[2] is changed in the loop to min{ n[2],d[1][j] } = 0. (We just did the same thing as before. That's the inefficiency.) We print (2,0).

Remark: For my application, it can be assumed that c[i][j]=d[i][j].

Answer 1

An interesting problem.

Note that time is necessarily proportional to the number of tuples that are to be enumerated. So it isn't possible to improve asymptotically on what you've got.

In terms of length of code, this can't be optimal, not by a long shot. You simply shouldn't have to code a separate for loop for every single i = 1..m

I may take a whack at the algorithm later; but to make a long story short, the running time will be exponential in m (except for trivial cases where constraints are equal to one.)