Algorithme pour convertir un tableau multidimensionnel à un tableau à une dimension

Il est assez facile de convertir un tableau en 2 dimensions d'un seul tableau multidimensionnel, mais comment puis-je convertir un tableau multidimensionnel de plus de 2 dimensions d'un tableau à une dimension? Par exemple, supposons que j'ai int [5][5][5] x et int [125] y et je veux mettre la valeur à x[3][4][2] à sa juste place dans y?

L'espoir qui fait sens.

OriginalL'auteur user436390 | 2010-08-31

  1. 33

    Quelques techniquement bonnes réponses ici déjà, mais voici une façon plus visuelle de la compréhension...

    OK, donc vous savez comment passer de la dimension 1 cas pour les 2 dimensions de cas.

    1-D tableau ressemble à ceci:

    int [5] :

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

    Et un tableau 2d ressemble à ceci:

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

    Vous pourrait image la conversion correspondant à l'1-D tableau comme ceci:

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

    Mais une autre façon de penser à ce sujet est à l'image du tableau d'origine, mais ré-étiquetés comme ceci:

    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]

    ...et si vous pensez de cette façon, les 3 dimensions de cas suit le même principe (et donc pour des dimensions supérieures, - il devient de plus en plus difficile à visualiser!):

    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]
    cool d'art ASCII.
    Merci! belle façon de l'illustrer!
    Plus de détails pour int[dimX][dimY][dimZ] : 1-D index de tableau [i * dimY*dimZ + j * dimZ + k]
    Cet exemple m'a inspiré pour comprendre la relation entre l'équation polynomiale et de la matrice(Vecteur).

    OriginalL'auteur Matthew Slattery

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

    et utile C truc:

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

    OriginalL'auteur Anycorn

  3. 2

    Il y a en fait une façon vraiment cool de penser à ce sujet que personne n'a posté ici encore.

    dans le cas le plus simple, vous pouvez l'imaginer X, Y, Z coordonnées que des chiffres dans un nombre imaginaire système que vous avez créé. Ces nombres sont écrits XYZ, de sorte que votre exemple [3][4][2] devrait être écrite comme: 342

    Ceux d'entre nous l'habitude de penser en Octal et Hexadécimal sont habitués à ce que cela ne veut pas dire trois cents, quatre des dizaines et 2, mais au lieu

    trois 64s, quatre 8, et deux 1s

    ou

    trois 256s, quatre 16s et 2

    C'est vraiment ce que votre nombre imaginaire système doit faire, mais chaque chiffre est à la base de la durée de l'autre côté du tableau, la prochaine fois inférieur à la base (à moins qu'il n'en est pas, dans ce cas, 1. La dernière longueur du tableau n'est pas utilisé dans ce calcul, mais au lieu de cela, seulement à la limite de votre boucle. Ordre dans ce calcul est basé sur la façon dont vous voulez traduire longueur côté en linéaire des éléments.

    Pour un 5x5x5 tableau, c'est facile:

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

    D'autres bases peuvent être plus complexes, en particulier avec les non-uniforme tailles, mais c'est juste une autre façon de penser le problème.

    Voici un non-uniforme 565 exemple:

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

    OriginalL'auteur SplinterReality

  4. 1

    Vous pouvez avoir différentes façons de carte multi-dimensions des tableaux dans des tableaux linéaires. Le truc, c'est que vous avez à choisir une convention. Allons-y avec la convention suivante. Le premier indice indique un bloc conteneur, le second spécifie un bloc dans l'une des précédentes conteneurs et, enfin, le troisième indicateur est le décalage à l'intérieur d'un bloc. Vous pouvez généraliser facilement pour les multi-dimensions, mais permet de garder à 3 pour cet exemple:

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

    OriginalL'auteur AraK

  5. -1

    Vous pouvez effectuer les opérations suivantes 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];
    }
}

    Ou de transformation en une n-dimensions tableau.

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

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

    OriginalL'auteur Rob Blackbourn