访问 N（未知）维矩阵中所有点的算法

Question

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

有关代码的一些信息： 该矩阵具有类似的值访问器（尽管这些并不真正相关）。

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

注意：参数 point 是索引数组，必须与维度数匹配，否则会引发异常。

有关矩阵结构的信息可以通过以下方式获得：

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

我想使用相对有效的算法迭代矩阵的所有可能点。

例如，在 2x3 2D 矩阵中，将访问以下六个点：
[0,0] [0,1] [0,2] [1,0] [1,1] [1,2]

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

Answer 1

您可以将矩阵视为一棵在叶子上具有所有值的树：

        

是矩阵

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

只需应用任何众所周知的树遍历解决方案即可。

---

这是一个递归解决方案（未经测试）：

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;
            }
        }
    }
}

将其转换为使用显式堆栈的迭代版本应该相当简单。

Answer 2

如果可以在运行时生成每个维度的索引值集合，则可以使用 Eric Lippert 的 LINQ 代码段，用于生成索引值的所有组合。

Eric 生成所有组合集合的方法：

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}));                
}

因此，对于您的 2x3 示例，

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

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

Answer 3

简单地递归迭代每个维度。例如，第一次调用迭代第一个维度的每个值，调用自身迭代第二个维度的每个值，依此类推，无论您有多少个维度。然后，基本情况（当没有更多维度时）是返回相关单元格中的值，而不是再次递归。

Answer 4

您可以使用混合基数表示，请参见 http://en.wikipedia.org/wiki/Mixed_radix< /a>

例如，如果有 4 个维度，长度分别为 4,3,2,7，则对应于索引 a,b,c,d，我们有数字 a+4*(b+3*(c+2* d））。从中恢复索引
数字 n 就像获取十进制数字一样，只是基数不同，即
a = n%4; n/=4； b = n%3； n /= 3； c = n%2； n/=2； d = n。

因此，您将有一个 for 循环（在本例中为 n=0..4*3*2*7-1），其中索引可以
如上所述从 n 中恢复。

然而，也许所有这些划分和模数意味着这不是那么有效。