Algorithm to convert a multi-dimensional array to a one-dimensional array

Question

It's easy enough to convert a 2-dimensional array to a single-dimensional array but how can I convert a multi-dimensional array of more than 2 dimensions to a one-dimensional array? For example, let's assume I have int [5][5][5] x and int [125] y and I want to place the value at x[3][4][2] in its right place in y?

Hope that makes sense.

Answer 1

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

and useful C trick:

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

Answer 2

You can have different ways to map multi-dimensional arrays into linear arrays. The thing is you have to pick a convention. Let's go with the following convention. The first index specifies a block container, the second specifies a block in one of the previous containers and finally the third index is the offset inside a block. You can generalize that easily for multi-dimensions but lets keep it at 3 for this example:

#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

A couple of technically good answers here already, but here's a more visual way of understanding it...

---

OK, so you know how to go from the 1-dimensional case to the 2-dimensional case.

A 1-D array looks like this:

int [5] :

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

And a 2-D array looks like this:

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 |     
|     |     |     |     |     |     
+-----+-----+-----+-----+-----+     

You could picture the conversion to the corresponding 1-D array like this:

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

But an alternative way of thinking about it is to picture the original array, but re-labelled - like this:

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]

...and if you think about it this way, the 3-dimensional case just follows the same principle (and so on for higher dimensions - it just gets harder and harder to visualise!):

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]