算法访问所有点N（未知）尺寸的矩阵 [英] Algorithm to visit all points in a matrix of N (unknown) dimensions

问题描述

我有一个多维矩阵，可以有任意数量的尺寸大于1。寻找一个高效的算法，可以访问矩阵中的每一个点。

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.

有关code的一些信息： 该矩阵具有价值访问一样（虽然这些都不是真正相关）。

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.

例如，在一个2×3矩阵2D以下六个点会被访问：
[0,0] [0,1] [0,2] [1,0] [1,1] [1,2]

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]

该算法必须工作到N维：2,3,4等。为了提高效率，我会最终使用一个 C＃迭代器返回点

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.

推荐答案

您可以查看您的基质中，有所有的值在叶一树：

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

＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;

           

是矩阵

[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.

这篇关于算法访问所有点N（未知）尺寸的矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！