0
$\begingroup$

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])
            }
        }...}}
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Aug 11, 2010 at 4:01
  • $\begingroup$ 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. $\endgroup$ Aug 11, 2010 at 4:05
  • $\begingroup$ 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. $\endgroup$
    – HDK
    Aug 12, 2010 at 2:08

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.