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.