将多维数组转换为一维数组的算法

Question

将二维数组转换为一维数组很容易，但是如何将多于2维的多维数组转换为一维数组？例如，假设我有int [5] [5] [5] x和int [125] y，并且我想将x [3] [4] [2]的值放在y的正确位置。

希望是有道理的。

Answer 1

m0,m1,.. are dimensions 
A(i,j,k,...) -> A0[i + j*m0 + k*m0*m1 + ...] 

和有用的C特技：

double *A; 
size_t m; 
#define A(i,j) A[(i) + (j)*m]; 

Answer 2

可以有不同的方式来映射多维数组成线性阵列。事情是你必须选择一个约定。遵循以下惯例。第一个索引指定一个块容器，第二个索引指定前一个容器中的一个块，最后第三个索引为块内的偏移量。你可以概括，可以轻松地进行多维度，但可以保持在3这个例子：

#include <cstddef> 

std::size_t linear_index 
    (std::size_t f, 
    std::size_t s, 
    std::size_t t, 
    std::size_t f_width, 
    std::size_t s_width) 
{ 
    return (f*f_width + s)*s_width + t; 
} 

Answer 3

一对夫妇在技术上很好的答案已经在这里，但这里的理解它一个更直观的方式...

---

好的，所以你知道如何从1维情况到2维情况。

A 1-d阵列看起来像这样：

int [5] : 

+-----+-----+-----+-----+-----+ 
| 0 | 1 | 2 | 3 | 4 | 
|  |  |  |  |  | 
+-----+-----+-----+-----+-----+ 

和2- d阵列看起来像这样：

int [5][5] : 

+-----+-----+-----+-----+-----+  
| 0,0 | 0,1 | 0,2 | 0,3 | 0,4 |  
|  |  |  |  |  |  
+-----+-----+-----+-----+-----+  
| 1,0 | 1,1 | 1,2 | 1,3 | 1,4 |  
|  |  |  |  |  |  
+-----+-----+-----+-----+-----+  
| 2,0 | 2,1 | 2,2 | 2,3 | 2,4 | 
|  |  |  |  |  |  
+-----+-----+-----+-----+-----+  
| 3,0 | 3,1 | 3,2 | 3,3 | 3,4 |  
|  |  |  |  |  |  
+-----+-----+-----+-----+-----+  
| 4,0 | 4,1 | 4,2 | 4,3 | 4,4 |  
|  |  |  |  |  |  
+-----+-----+-----+-----+-----+  

您所能图像转化为相应的1- d像这样的阵列：

+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+- - - 
| 0,0 | 0,1 | 0,2 | 0,3 | 0,4 | 1,0 | 1,1 | 1,2 | 1,3 | 1,4 | etc. 
|  |  |  |  |  |  |  |  |  |  | 
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+- - - 
          vvv 
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+- - - 
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | etc. 
|  |  |  |  |  |  |  |  |  |  | 
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+- - - 

但是另一种思考方式回合它是画面中的原始数组，但重新标记 - 这样的：

int [5][5] : 

+-----+-----+-----+-----+-----+  +-----+-----+-----+-----+-----+ 
| 0,0 | 0,1 | 0,2 | 0,3 | 0,4 |  | 0 | 1 | 2 | 3 | 4 | 
|  |  |  |  |  |  |  |  |  |  |  | 
+-----+-----+-----+-----+-----+  +-----+-----+-----+-----+-----+ 
| 1,0 | 1,1 | 1,2 | 1,3 | 1,4 |  | 5 | 6 | 7 | 8 | 9 | 
|  |  |  |  |  |  |  |  |  |  |  | 
+-----+-----+-----+-----+-----+  +-----+-----+-----+-----+-----+ 
| 2,0 | 2,1 | 2,2 | 2,3 | 2,4 | => | 10 | 11 | 12 | 13 | 14 | 
|  |  |  |  |  |  |  |  |  |  |  | 
+-----+-----+-----+-----+-----+  +-----+-----+-----+-----+-----+ 
| 3,0 | 3,1 | 3,2 | 3,3 | 3,4 |  | 15 | 16 | 17 | 18 | 19 | 
|  |  |  |  |  |  |  |  |  |  |  | 
+-----+-----+-----+-----+-----+  +-----+-----+-----+-----+-----+ 
| 4,0 | 4,1 | 4,2 | 4,3 | 4,4 |  | 20 | 21 | 22 | 23 | 24 | 
|  |  |  |  |  |  |  |  |  |  |  | 
+-----+-----+-----+-----+-----+  +-----+-----+-----+-----+-----+ 

2-D array index [i][j]   => 1-D array index [i*5 + j] 

...如果你想想这种方式，三维情况下，只需遵循同样的原则（等对于更高的尺寸 - 它变得越来越难以可视化！）：

int [5][5][5] : 

+-----+-----+-----+-----+-----+   +-----+-----+-----+-----+-----+ 
|+-----+-----+-----+-----+-----+  |+-----+-----+-----+-----+-----+ 
||+-----+-----+-----+-----+-----+  ||+-----+-----+-----+-----+-----+ 
|||+-----+-----+-----+-----+-----+  |||+-----+-----+-----+-----+-----+ 
||||1,0,0|1,0,1|1,0,2|1,0,3|1,0,4|  |||| 25 | 26 | 27 | 28 | 29 | 
|||| +-----+-----+-----+-----+-----+ |||| +-----+-----+-----+-----+-----+ 
|||+---|0,0,0|0,0,1|0,0,2|0,0,3|0,0,4| |||+---| 0 | 1 | 2 | 3 | 4 | 
||||1,1|  |  |  |  |  | |||| 30|  |  |  |  |  | 
|||| +-----+-----+-----+-----+-----+ |||| +-----+-----+-----+-----+-----+ 
|||+---|0,1,0|0,1,1|0,1,2|0,1,3|0,1,4| |||+---| 5 | 6 | 7 | 8 | 9 | 
||||1,2|  |  |  |  |  | |||| 35|  |  |  |  |  | 
|||| +-----+-----+-----+-----+-----+ |||| +-----+-----+-----+-----+-----+ 
|||+---|0,2,0|0,2,1|0,2,2|0,2,3|0,2,4|=>|||+---| 10 | 11 | 12 | 13 | 14 | 
||||1,3|  |  |  |  |  | |||| 40|  |  |  |  |  | 
|||| +-----+-----+-----+-----+-----+ |||| +-----+-----+-----+-----+-----+ 
+||+---|0,3,0|0,3,1|0,3,2|0,3,3|0,3,4| +||+---| 15 | 16 | 17 | 18 | 19 | 
+||1,4|  |  |  |  |  | +|| 45|  |  |  |  |  | 
    +| +-----+-----+-----+-----+-----+ +| +-----+-----+-----+-----+-----+ 
    +---|0,4,0|0,4,1|0,4,2|0,4,3|0,4,4|  +---| 20 | 21 | 22 | 23 | 24 | 
     |  |  |  |  |  |   |  |  |  |  |  | 
     +-----+-----+-----+-----+-----+   +-----+-----+-----+-----+-----+ 

3-D array index [i][j][k]    => 1-D array index [i*5*5 + j*5 + k] 

Answer 4

您可以在C＃中执行以下操作。或者转换成n维数组。

public static class ArrayExtensions 
{ 
    public static Array CreateArray<T>(this T[] array1d, params int[] bounds) 
    { 
     var arrayNd = Array.CreateInstance(typeof(T), bounds); 

     var indices = new int[bounds.Length]; 
     for (var i = 0; i < array1d.Length; ++i) 
     { 
      arrayNd.SetValue(array1d[i], indices); 

      for (int j = 0; j < bounds.Length; ++j) 
      { 
       if (++indices[j] < bounds[j]) 
        break; 
       indices[j] = 0; 
      } 
     } 

     return arrayNd; 
    } 
} 

并进行测试。

int[] array3d = 
    new[] 
    { 
     0, 1, 2, 3, 
     4, 5, 6, 7, 
     8, 9, 10, 11, 

     12, 13, 14, 15, 
     16, 17, 18, 19, 
     20, 21, 22, 23 
    }; 

var copied3d = (int[, ,])array3d.CreateArray(4, 3, 2); 
var indexer3d = new ArrayIndexer(4, 3, 2); 

for (int i = 0; i < 4; ++i) 
{ 
    for (int j = 0; j < 3; ++j) 
    { 
     for (int k = 0; k < 2; ++k) 
     { 
      var x = indexer3d.FastIndex(array3d, i, j, k); 
      var y = copied3d[i, j, k]; 
      Debug.Print("Array[{0},{1},{2}] = {3} and {4} match = {5}", i, j, k, x, y, x == y); 
     } 
    } 
} 

Answer 5

实际上有一种非常酷的方式去思考这个没有人在这里发布的。

在最简单的情况下，您可以将X，Y，Z坐标想象为您创建的虚数系统中的数字。这些数字写成XYZ，所以你的例子[3] [4] [2]会写成：342

我们那些习惯于在八进制和十六进制中思考的人习惯于认为这并不意味着三百， 4十位和2个的，而是

3个64S，四件787-8和两个1

或

3 256S，四米16和2个1

这真是你的虚数系统需要做的，但每个数字是基础数组中相应边的长度，乘以下一个较低的基数（除非没有，在这种情况下，1.在该计算中不使用最后一个数组长度，而是仅限制循环。此计算中的排序基于您想如何将边长转换为线性元素。

对于一个5×5×阵列，这是很容易：

 
    25s | 5s | 1s 
* 3 | 4 | 2 
    ----+----+--- 
    75 + 20 + 2 = 97 

其他基地可能比较复杂，尤其是在非均匀的尺寸，但它是思考这个问题的另一种方式。

这里的一个非均匀565例如：

 
    30s | 5s | 1s 
* 3 | 4 | 2 
    ----+----+--- 
    90 + 20 + 2 = 102