Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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])
            }
        }...}}
share|improve this question
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.