Expert: Josh - 3/4/2011

Question
Hello,

I have not worked on finding math equations based on some logic for many years. I would like to seek help on a problem that I'm currently working on.

I have two sets A and B, where A = B = {1,2,3,4,5}.
Now, I compute the set C = A X B, and would like to have an ordering on the set C = {(a_1,b_1)...(a_m,b_n)} with the following logic:

First approach:

(i) order the tuples in set C sorted with highest value of b_j (ie. starting with 5; as in (1,5) appears before (1,4)) and
(ii) whenever two tuples have the same value for b_j (ie. (1,5) and (2,5)), then the tuple with greater difference (1,5) appears before (2,5).

I need to compute an equation that gives some value between the interval [0,1] so that the final ordering of set C is as follows: {(1,5), (2,5), (3,5), (4,5), (1,4), (2,4), (3,4), (1,3), (2,3), (1,2)}.

Second approach:

Similar to the above case, I would like to sort set C with lowest value of a_i (ie. starting with 5; as in (1,5) appears before (2,5)) and
(ii) whenever two tuples have the same value for a_i (ie. (1,5) and (1,4)), then the tuple with greater difference (1,5) appears before (2,5).

I need to compute another equation that gives some value between the interval [0,1] so that the final ordering of set C is as follows: {(1,5), (1,4), (1,3), (1,2), (2,5), (2,4), (2,3), (3,5), (3,4), (4,5)}.

Many thanks!

Gaven

Answer
Hi Gaven,

Regarding the first approach, the simplest way of following the sequence is to execute the following program.

Let N be the number of rows in the problem. Here N=5.
Let c, r and i all be integer variables.

(Initialization)
* SET index i=1.

(Loop)
FOR column c=N to c=2 (in decreasing order)
   FOR row r=1 to r=c-1 (in increasing order)
       (Compute the i^{th} entry in the sequence)
       * SET S[i]=(r,c)
       * INCREASE i by 1.
   END
END

To visualize this, draw a 5x5 grid. The cells of interest are labeled
[    ] [(1,2)] [(1,3)] [(1,4)] [(1,5)]
[    ] [     ] [(2,3)] [(2,4)] [(2,5)]
[    ] [     ] [     ] [(3,4)] [(3,5)]
[    ] [     ] [     ] [     ] [(4,5)]
[    ] [     ] [     ] [     ] [     ]
and visited in the following order.
[    ] [  10 ] [  8  ] [  5  ] [  1  ]
[    ] [     ] [  9  ] [  6  ] [  2  ]
[    ] [     ] [     ] [  7  ] [  3  ]
[    ] [     ] [     ] [     ] [  4  ]
[    ] [     ] [     ] [     ] [     ]

To formulate a function, I will enumerate each cell using the row and column indexes (viz., with a_i and b_j). Applying k = N*b_j + (N-a_i), we get
[    ] [  14 ] [  19 ] [  24 ] [  29 ]
[    ] [     ] [  18 ] [  23 ] [  28 ]
[    ] [     ] [     ] [  22 ] [  27 ]
[    ] [     ] [     ] [     ] [  26 ]
[    ] [     ] [     ] [     ] [     ]

| For instance, with the middle entry in the first row, we have
| a_i=1, b_j=3. So, k(1,3)=5*3+(5-1)=19.

There is nothing unique about this numbering system, except the sequence is essentially sorted in decreasing order. There are two remaining problems. First, the cells we do not wish to visit are also enumerated (although this is not shown). This can be handled by imposing an inequality on the row and column indexes (we will get to this in a moment). Second, we want to map each (a_i,b_j) to a value in the interval [0,1]. This can be achieved by normalizing the expression of "k". If each enumerated value is divided by (N+1)*N-1, everything will fit into this range.

So, the function may be written as
f(a_i,b_j) = { [N*(b_j+1)-a_i] / [(N+1)*N-1],  if a_i < b_j
            { 0                            ,  otherwise

The second part is handled in the same way. The visiting order is
[    ] [  4  ] [  3  ] [  2  ] [  1  ]
[    ] [     ] [  7  ] [  6  ] [  5  ]
[    ] [     ] [     ] [  9  ] [  8  ]
[    ] [     ] [     ] [     ] [ 10  ]
[    ] [     ] [     ] [     ] [     ]

The intermediate step is to enumerate (a_i,b_j) as k = N*(N-a_i)+b_j. We get
[    ] [  22 ] [  23 ] [  24 ] [  25 ]
[    ] [     ] [  18 ] [  19 ] [  20 ]
[    ] [     ] [     ] [  14 ] [  15 ]
[    ] [     ] [     ] [     ] [  10 ]
[    ] [     ] [     ] [     ] [     ]
Applying the same logic, the final function may be written as

f(a_i,b_j) = { [N*(N-a_i)+b_j] / [N*N],  if b_j > a_i
            { 0                      ,  otherwise

The sequence is obtained by sorted all non-zero entries f(a_i,b_j) in decreasing order.

By the way, the program for the second part is also pretty straight forward...perhaps easier than coming up with an expression for the function.

SET i=1.
FOR r=1 to c=N-1      (in increasing order)
   FOR c=N to c=r+1    (in decreasing order)
       SET S[i]=(r,c)
       INCREASE i by 1.
   END
END


Cheers,

Josh