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

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开发者_StackOverflow sense.

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]

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

There's actually a really cool way to think about this which noone has posted here yet.

in the simplest case, you can imagine X, Y, Z coordinates as digits in an imaginary number system you created. These numbers are written XYZ, so your example [3][4][2] would be written as: 342

Those of us used to thinking in Octal and Hexadecimal are accustomed to thinking this doesn't mean three hundred, four tens and 2 ones, but instead

three 64s, four 8s, and two 1s

or

three 256s, four 16s and 2 ones

This is really what your imaginary number system needs to do, but each numeral is the base of the length of that respective side in the array, times the next lower base (unless there is none, in which case, 1. The last array length is not used in this calculation, but instead, only to limit your looping. Ordering in this calculation is based on how you want to translate side lengths into linear elements.

For a 5x5x5 array, this is easy:

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

Other bases may be more complex, especially with non-uniform sizes, but it's just another way of thinking about the problem.

Here's a non-uniform 565 example:

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

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

You could do the following in C#.

public class ArrayIndexer
{
    private readonly int[] _bounds;
    private readonly int[] _sum;

    public ArrayIndexer(params int[] bounds)
    {
        _bounds = bounds;

        // Pre-compute bounds sums for speed.
        _sum = new int[bounds.Length - 1];
        for (int i = 1, sum = _bounds[i - 1]; i < _bounds.Length; ++i, sum *= _bounds[i - 1])
            _sum[i-1] = sum;
    }

    public T Index<T>(T[] array, params int[] indices)
    {
        if (indices.Length != _bounds.Length)
            throw new ArgumentException("There should be as many indices as bounds", "indices");

        var index = indices[0];
        for (int i = 1, sum = _bounds[i - 1]; i < indices.Length; ++i, sum *= _bounds[i - 1])
            index += sum * indices[i];
        return array[index];
    }

    public T FastIndex<T>(T[] array, params int[] indices)
    {
        if (indices.Length != _bounds.Length)
            throw new ArgumentException("There should be as many indices as bounds", "indices");

        var index = indices[0];
        for (int i = 1; i < indices.Length; ++i)
            index += _sum[i-1] * indices[i];
        return array[index];
    }
}

Or to transform into an n-dimensional array.

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

And to test.

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