Traverse a matrix using a linear index to get an evenly distributed values sample

Question

I'm looking for an algorithm idea on how to traverse a matrix using a linear index while avoiding row/column based traversals to get a more diverse distribution of values.

To understand this better, think of an image that's split in blocks, with N rows & M columns. I need to process each image block sequentially (from 1 to NxM) but I don't know in advance what the processing time will be for each block ( blocks that are close together tend to have a similar processing time, with small variations).

During processing, I need to be able to estimate as best as possible the remaining processing time based on the number of blocks that have already been processed & their associated processing time. For this reason, traversing the blocks by columns or by rows will not give an accurate estimation so I need to find another way of traversing the matrix that would pick values from different zones of the image.

It's also important to be able to determine the blocks processing order based on a linear index (from 1 to NxM), without calculating them in advance. The algorithm that returns the row & column corresponding to the linear index should be as fast as possible.

Shorter version of the question

For a liner index named idx, I need to get a corresponding row & column pair from a matrix with N rows & M columns while avoiding a row/column based traversal.

For each idx between 1 and NxM, the algorithm would return a [row, column] pair so that all the rows & columns combinations are returned exactly once.

Example

(the values in the matrix represent the linear index's value that's associated with that row&column position)

 1 17 13 9 5
 6 2 18 14 10
11 7 3 19 15
16 12 8 4 20

The above example is for a diagonal traversal that would produce a better distribution of values that a row/column based traversal.

Another possible solution would be to split the matrix into smaller blocks & traverse those blocks in rows/columns. For example a 4x5 matrix could be virtually split into 2x2 blocks and those smaller blocks could be traversed by rows or columns (e.g. idx(1) = block1[1, 1], idx(2) = block2[1, 1], etc.). The traversal would look something like this:

 1 13 | 3 15 | 5
 7 17 | 9 18 | 11
------+-------+---
 2 14 | 4 16 | 6
 8 19 | 10 20 | 12

Any other traversal ideas are welcomed.

Ideally, this algorithm would translate to a math formula to calculate the row & column based on the linear index, possibly with a few conditions (IF statements) to compensate for missing values, etc.

• kevin cline: You gave two solutions. What's your question?
• Dan C.: @kevincline I'd like to see if anyone can suggest any other solution for this problem (possibly a "popular" solution that I do not know about) and to get any tips on the best way to calculate the [row, column] combination from the index (although I proposed two possible traversals, I haven't figured out yet the formulas/algorithms for those traversals)

Answer 1

Put all integers from 0 to NxM-1 into an array, shuffle that array randomly and pick the results one after another (mapping to row/column could be anything trivial like row=idx mod M , col=idx/M).

A good shuffle algorithm is Fisher-Yates shuffling, see here.

• Dan C.: Although this would offer a good distribution of values, it involves generating & storing the shuffled array. I'd like to find a solution that can calculate the row & col from idx on the fly, without having to generate all the possible values up to that point (assume that N & M can be quite large so generating & storing an array with too many values is not the best approach)

Answer 2

You indicated that you don't want to do row/column traversal, but that could be a useful method. Calculate an index change value for the array so each new index translates into a row/column position that samples a different area of the matrix. The only requirement is that the index change value must be coprime with the array length. This guarantees that each matrix position will be chosen once without calculating them in advance. The first index is 0 which is 0,0 , but could be calculated from m/2,n/2 to center it.

// matrix dimensions are
// image height and width
var m = 600;
var n = 800;
// length of image array (number of matrix elements)
var l = m * n;
// potential coprime value
// for this expression
// number of rows is smaller of m and n
// while number of columns is larger of m and n
var p = floor( ( floor( min( m, n ) * 0.4) + 0.6) * max( m, n ) );
// greatest common denominator
// Euclidian algorithm
var gcd = function( a, b ){
 if( b === 0 ){
 return a;
 }
 return gcd( b, a % b );
}
// find coprime equal to or greater
while( p > 1 && gcd( l, p ) > 1 ){
 // increase coprime by 1
 p ++;
}
// starting index
var s = 0;
// center index
// center row plus center column
s = floor(m/2)*n + floor(n/2);
// loop through number of index positions
for( var j = 0; j < l; j ++ ){
 // index is start plus j times coprime mod array length
 var i = ( s + j * p ) % l;
 // row is index divided by number of columns rounded down
 var r = floor( i / n );
 // column is index mod number of columns
 var c = i % n;
}