# Enumerating m-tuples of Integers Subject to Implication Constraints

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:

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])
}
}...}}
-
There are more efficient ways to code it, at least; any time you want to list $m$-tuples and find yourself writing essentially $m$ for loops, you're being inefficient in that sense -- not necessarily in runtime complexity. If $m$ ever gets very large (which it better hadn't) you could be using another, sorted, data structure to binary search among the c_ij to see if you're violating any of them (i.e. changing some n[j]). How did this come up? –  Eric Tressler Aug 11 '10 at 4:01
I ask because I can't imagine why you'd want such a list. Your innermost operation is print, so you're going to be generating a lot of text, and the description of the set seems more useful than the output list. –  Eric Tressler Aug 11 '10 at 4:05
As far as coding efficiency goes, my solution can rewritten more compactly as a recursion. The a_i are the exponents of the possible prime factors of an unknown ideal. The application I have in mind treats each tuple as a case. Further computations are to be done for each case. For me, the list is the important thing. –  HDK Aug 12 '10 at 2:08