Algorithm to visit all points in a matrix of N (unknown) dimensions.

Question

I have a multidimensional matrix that can have any number of dimensions greater than one. Looking for an efficient algorithm that can visit every point in the matrix.

Some info about the code: The matrix has value accessors like (although these aren't really relevant).

object value = matrixInstance.GetValue(int[] point);   
matrixInstance.SetValue(object value, int[] point);  

Note: Argument point is array of indexes and must match # of dimensions or an exception is thrown.

Information about the matrix structure can be garnered by:

int numDims = matrixInstance.Rank; //# dimensions
int sizeDim = matrix.getRankSize(int index); // length of specified dimension

I want to iterate over all possible points of the matrix using a relatively efficient algorithm.

For example, in a 2x3 2D matrix the following six points would be visited:
[0,0] [0,1] [0,2] [1,0] [1,1] [1,2]

The algorithm must work up to N dimensions: 2,3,4,etc. For efficiency I'll end up using a C# iterator to return the points.

Answer 1

You can view your matrix an a tree that has all of its values at the leaves:

           

is the matrix

[0,0] = 'A'
[0,1] = 'B'
[1,0] = 'C'
[1,1] = 'D'

Just apply any well-known tree traversal solution.

---

Here is a recursive solution (untested):

IEnumerable<Point> GetPoints(Matrix matrix, int[] indexes)
{
    if (indexes.Length == matrix.Rank)
    {
        yield return matrix.GetValue(indexes);
    }
    else
    {
        for (int i = 0; i < matrix.GetRankSize(indexes.Length); i++)
        {
            foreach (var point in
                GetPoints(matrix, indexes.Concat(new int[] { i }).ToArray())
            {
                yield return point;
            }
        }
    }
}

It should be fairly trivial to convert this to an iterative version that uses an explicit stack.

Answer 2

If you can generate a collection of index values for each dimension at run time, then you can use Eric Lippert's LINQ snippet to generate all combinations of the index values.

Eric's method to produce a collection of all combinations:

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) 
{ 
  IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
  return sequences.Aggregate( 
    emptyProduct, 
    (accumulator, sequence) =>  
      from accseq in accumulator  
      from item in sequence  
      select accseq.Concat(new[] {item}));                
}

So, for your 2x3 example,

int [ , ] dimensions= { { 0, 1}, { 0, 1, 2 } } ;
var allMatrixCells = CartesianProduct<int>(dimensions);

foreach(var cellLocation in allMatrixCells )
{
 ...
}

Answer 3

Simply recursively iterate over each dimension. Eg, the first invocation iterates over every value for the first dimension, calling itself to iterate over every value for the second dimension, and so forth for however many dimensions you have. Then, the base case (when there are no more dimensions) is to return the value in the relevant cell, rather than recursing again.

Answer 4

You could use a mixed radix representation, see eg http://en.wikipedia.org/wiki/Mixed_radix

For example if you had 4 dimensions with lengths 4,3,2,7 say then corresponding to the indices a,b,c,d we have the number a+4*(b+3*(c+2*d)). To recover the indices from a number n is just like getting the decimal digits, except the base varies, ie a = n%4; n /=4; b = n%3; n /= 3; c = n %2; n/=2; d = n.

So you would have one for loop (in this case for n=0..4*3*2*7-1) in which the indices could be recovered from n as above.

However perhaps all those divisions and moduli would mean this isn't so efficient.