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

我有一个多维矩阵，其维数可以大于1。寻找可以访问矩阵中每个点的高效算法。访问N（未知）维矩阵中所有点的算法

关于代码的一些信息：该矩阵具有类似的值存取权（虽然这些并不真正相关）。

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

注意：参数点是索引的阵列，并且必须匹配尺寸＃或抛出异常。

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

我想遍历使用相对高效的算法，矩阵的所有可能的点：

关于矩阵结构的信息可以通过囊括。

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

该算法必须工作到N维：2,3,4等。为了提高效率，我最终会使用C# iterator来返回积分。

来源

2010-08-24 John K

您可以查看矩阵的具有所有其值在叶子树：

是矩阵

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

它应该是相当琐碎将此转换到使用显式堆栈的迭代版本。

来源

2010-08-24 19:24:33 dtb

我最终使用递归函数，然后将其转换为基于堆栈的实现，如您所述。不过，我从头开始编写代码，以便您的代码保持未经测试。 – 2010-09-03 03:50:55

如果您可以在运行时为每个维度生成一组索引值，则可以使用Eric Lippert's LINQ snippet生成索引值的所有组合。

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) 
{ 
... 
}

来源

2010-08-24 20:44:05 mbeckish

LOL。我只是在研究完全相同的解决方案。良好的工作:) – LBushkin 2010-08-24 20:58:02

简单的递归每个维度迭代。例如，第一个调用迭代第一个维度的每个值，调用它自己遍历第二维度的每个值，等等。然后，基本情况（当没有更多维度时）将返回相关单元格中的值，而不是再次递归。

来源

2010-08-24 23:23:53

你可以使用一个混合基表示，例如见http://en.wikipedia.org/wiki/Mixed_radix

例如，如果你有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从n中恢复为。

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

来源

2010-08-25 10:33:19 dmuir

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

回答

相关问题