How to convert an M-dimensional array to an N-dimensional array?

Question

Inspired by arr2D[i][j] and arr1D[i * k + j] after reading this post and the comments under it, I would like to know an algorithm that can change the dimensions of any array.

Let me try to formalize it:

Input:

1. An M-dimensional container A

2. The dimensions D of the container (size)

3. Target dimension N

Output:

If N > 0 then return an N-dimensional container B with the same contents as A in order otherwise return an error code.

Note:

You may choose any optimal size for the N-dimensional container.

Edit:

I don't need any fully working code. I'm asking if there's any algorithm that does this?

Answer 1

Converts [100] to [10][10]:

#include <iostream>

typedef int (*parray)[10];

parray foo (int *in) {
    return (parray)in;
}

int main()
{
    int in[100];
    in[55] = 42;
    int (*out)[10] = foo(in);
    std::cout << out[5][5] << std::endl;

    return 0;
}

Answer 2

Your original M-dimensional container is A.

We want to create a new N-dimensional container B that will hold all content of A.

First we have to figure out a mapping where we can easily find the same element in A and in B.

Let's use some examples to deduce how the mapping could be:

(1) M = 2, N = 1

A: a * b    B: c
we can set the dimension c to be a * b, thus we have
A[i][j] = B[i * c + j]

(2) M = 3, N = 1

A: a * b * c    B: d
d = a * b * c
A[i][j][k] = B[(i * b * c) + (j * c) + k]

(3) M = 3, N = 2

A: a * b * c    B: d * e
d = a, e = b * c
A[i][j][k] = B[i][j * c + k]

(4) M = 4, N = 1

A: a * b * c * d    B: e
e = a * b * c * d
A[i][j][k][l] = B[(i * b * c * d) + (j * c * d) + (k * d) + l]

(5) M = 5, N = 4

A: a * b * c * d * e    B: u * v * w * x
u = a, v = b, w = c, x = d * e
A[i][j][k][l][m] = B[i][j][k][(l * e) + m]

(6) M = 5, N = 2

A: a * b * c * d * e    B: f * g
f = a, g = b * c * d * e
A[i][j][k][l][m] = B[i][(j * c * d * e) + (k * d * e) + (l * e) + m]

---

If A has M dimensions a1, a2, ..., aM and B has N dimensions b1, b2, ..., bN, we can say that:

if M > N, then for all 0 < i < N, bi = ai and bN = aN * aN+1 * ... * aM.

This way we know how to create B and the size of each dimension of it.

With the mapping function shown in the examples, you can easily convert any M-dimension matrix to a N-dimension matrix.

If M < N, you can do the same thing but in opposite direction.

Answer 3

As you don't need a code, let me explain how you could do it with templates.

Say you have an D-dimensional array of size n_{0},...,n_{d-1} you can always remove one dimension by merging two of them multiplying the sizes. Examples: a[5][4][3] contains 60 elements, thus b[20][3] or c[5][12] (for simple cases, because you may even construct d[15][4] and any permutations) can easily contains the same elements as a, the mapping of indices is also such obvious...

Now using C++ doing it it much more tricky but you will need: variadic templates and template metaprogramming.

Variadic template to define an array type of any dimension you like, and template metaprogramming to define an operator to map a D-dimensional array to a N-dimensional one. (I may say that it will not be easy, but a very -hard- good exercise in template metaprogramming).

Answer 4

So you just want to reformat your matrices while no data is changed. As I hinted in my comment the simplest is to use 1D array mid step for converting from M to N dimensions.

The other answers here are on the same track but are lacking the whole math ... they have just examples up to some small dimension without universal equation so here it is:

To convert between A[A0][A1]...[A(M-1)] and X[A0*A1*...*A(M-1)] where A0,A1,...A(M-1) are the dimension sizes of your container (resolution) simply do this:

// M-D -> 1D
x = a0
   +a1*A0
   +a2*A0*A1
   ...
   +a(M-1)*A0*A1*...*A(M-2);

// 1D -> M-D   
q=x;
a0 = q%A0; q/=A0;
a1 = q%A1; q/=A1;
a2 = q%A2; q/=A2;
...
a(M-1) = q%A(M-1); q/=A(M-1);

where a0,a1,...a(M-1) and x are the indexes in the arrays.

You actually do not need to convert the M-D array into 1D and then back to N-D its enough to just convert the indexes so:

for (a0=0;a0<A0;a0++)
 for (a1=0;a1<A1;a1++)
  ...
   for (a(M-1)=0;a(M-1)<A(M-1);a(M-1)++)
      {
      // M-D -> 1D
      x = a0
         +a1*A0
         +a2*A0*A1
         ...
         +a(M-1)*A0*A1*...*A(M-2);
      // 1D -> N-D   
      q=x;
      b0 = q%B0; q/=B0;
      b1 = q%B1; q/=B1;
      b2 = q%B2; q/=B2;
      ...
      b(N-1) = q%B(N-1); q/=B(N-1);
      // copy A -> B
      B[b0][b1]...[b(N-1)] = A[A0][A1]...[A(M-1)];
      }

Do not forget that the sizes must be:

A0*A1*...*A(M-1) <= B0*B1*...*B(N-1)

otherwise you will access array out of its bounds as the data in A will not fit into B.

In case you got dynamic dimensionality you can use:

• dynamicaly nested for loop nested_for