algorithm - resueltos - Algoritmo para convertir una matriz multidimensional en una matriz unidimensional
vectores en java ejemplos (5)
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? 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.
Puede tener diferentes formas de mapear 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. Puedes generalizarlo fácilmente para múltiples dimensiones, pero mantenlo en 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;
}
Un par de respuestas técnicamente buenas aquí ya, pero aquí hay una forma más visual de entenderlo ...
De acuerdo, entonces sabes cómo pasar del caso unidimensional al caso bidimensional.
Una matriz 1-D se ve así:
int [5] :
+-----+-----+-----+-----+-----+
| 0 | 1 | 2 | 3 | 4 |
| | | | | |
+-----+-----+-----+-----+-----+
Y una matriz 2-D se ve así:
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 |
| | | | | |
+-----+-----+-----+-----+-----+
Puede imaginar la conversión a la matriz 1-D correspondiente de esta manera:
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+- - -
| 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 es imaginar el arreglo original, pero etiquetado de nuevo, como este:
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 lo piensas de esta manera, el caso tridimensional solo sigue el mismo principio (y así sucesivamente para dimensiones más altas, ¡se vuelve más y 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]
m0,m1,.. are dimensions
A(i,j,k,...) -> A0[i + j*m0 + k*m0*m1 + ...]
y truco C útil:
double *A;
size_t m;
#define A(i,j) A[(i) + (j)*m];
De hecho, hay una forma genial de pensar acerca de 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 creó. 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 trescientas, cuatro decenas y dos unidades, sino que
tres 64s, cuatro 8s y dos 1s
o
tres 256, cuatro, 16 y 2
Esto es realmente lo que su sistema de números imaginarios necesita hacer, pero cada numeral 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. El orden en este cálculo se basa en la forma en que desea convertir las longitudes de los lados en elementos lineales.
Para una matriz de 5x5x5, esto es fácil:
25s | 5s | 1s * 3 | 4 | 2 ----+----+--- 75 + 20 + 2 = 97
Otras bases pueden ser más complejas, especialmente con tamaños no uniformes, pero es solo otra forma de pensar sobre el problema.
Aquí hay un ejemplo no uniforme de 565:
30s | 5s | 1s * 3 | 4 | 2 ----+----+--- 90 + 20 + 2 = 102
Puedes 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 para probar.
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);
}
}
}