Algoritmo para convertir una matriz multidimensional en una matriz unidimensional

Question

Es bastante fácil convertir una matriz bidimensional en una matriz unidimensional, pero ¿cómo puedo convertir una matriz multidimensional de más de 2 dimensiones en una matriz unidimensional? matriz unidimensional? Por ejemplo, supongamos que tengo int [5] [5] [5] x y int [125] y y quiero colocar el valor en x [3] [4] [2] en su lugar correcto en y?

Espero que tenga sentido.

Answer 1

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

C y útil truco:

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

Answer 2

puede tener diferentes formas de asignar matrices multidimensionales en matrices lineales. El caso es que debes elegir una convención. Vamos con la siguiente convención. El primer índice especifica un contenedor de bloques, el segundo especifica un bloque en uno de los contenedores anteriores y finalmente el tercer índice es el desplazamiento dentro de un bloque. Se puede generalizar fácilmente para que multidimensiones pero permite mantenerlo a 3 para este ejemplo:

#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

Un par de buenos técnicamente respuestas aquí ya, pero aquí está una manera más visual de entenderlo ...

---

OK, para que sepa cómo pasar del caso unidimensional al caso bidimensional.

Una matriz 1-D se parece a esto:

int [5] : 

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

Y una matriz 2-D se parece a esto:

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

Usted podía imagen de la conversión a la correspondiente 1-D matriz como esta:

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

Pero una forma alternativa de pensar una pelea es de imaginar la matriz original, pero re-etiquetados - como esto:

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] 

... y si se piensa en ello de esta manera, el caso de 3 dimensiones se limita a seguir el mismo principio (y así sucesivamente para dimensiones más altas, ¡cada vez es más difícil de visualizar!):

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

Puede hacer lo siguiente en 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]; 
    } 
} 

O para transformar en una matriz n-dimensional.

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

Y a prueba.

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

En realidad, hay una forma genial de pensar en esto que nadie ha publicado hasta ahora.

en el caso más simple, puede imaginar las coordenadas X, Y, Z como dígitos en un sistema de números imaginarios que ha creado.Estos números están escritos XYZ, por lo que su ejemplo [3] [4] [2] se escribiría como: 342

Los que estábamos acostumbrados a pensar en Octal y Hexadecimal estamos acostumbrados a pensar que esto no significa trescientos, cuatro decenas y 2 unidades, pero en lugar

tres 64s, cuatro 8s, y dos 1s

o

tres 256s, cuatro 16s y 2 los

Esto es realmente lo que su sistema de número imaginario tiene que hacer, pero cada número es la base de la longitud de ese lado respectivo en la matriz, multiplicado por la siguiente base inferior (a menos que no haya ninguno, en cuyo caso, 1. La última longitud de la matriz no se utiliza en este cálculo, sino que solo limita su bucle). Ordenar en este cálculo se basa en cómo desea traducir las longitudes laterales en elementos lineales.

Para una matriz 5x5x5, esto es fácil:

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

Otras bases pueden ser más complejos, especialmente con tamaños no uniformes, pero es sólo otra manera de pensar en el problema.

Aquí hay una no uniforme 565 ejemplo:

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