將多維數組轉換爲一維數組的算法

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