Алгоритм преобразования многомерного массива в одномерный массив

Question

Достаточно просто преобразовать двумерный массив в одномерный массив, но как я могу преобразовать многомерный массив из более чем двух измерений в одномерный массив?Например, давайте предположим, что у меня есть int [5] [5] [5] x и int [125] y, и я хочу поместить значение в x [3] [4] [2] в нужном месте в y?

Надеюсь, это имеет смысл.

Answer 1

Здесь уже есть пара технически хороших ответов, но вот более наглядный способ понять это ...

---

ОК, так что вы знаете, как перейти от 1-мерного случая к 2-мерному.

1-D массив выглядит так:

int [5] :

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

И двумерный массив выглядит так:

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

Вы могли бы представить преобразование в соответствующий 1-D массив следующим образом:

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

Но альтернативный способ размышления об этом состоит в том, чтобы изобразить исходный массив, но переименовать - вот так:

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]

... и если вы думаете об этом таким образом, трехмерный случай просто следует тому же принципу (и так для более высоких измерений - его становится все труднее и труднее визуализировать!):

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 2

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

и полезный трюк C:

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

Answer 3

На самом деле есть действительно крутой способ думать об этом, который еще никто не опубликовал здесь.

В простейшем случае вы можете представить координаты X, Y, Z как цифры в воображаемой системе счисления, которую вы создали.Эти числа написаны XYZ, поэтому ваш пример [3] [4] [2] будет записан как: 342

Те из нас, кто привык думать в шестнадцатеричном и шестнадцатеричном, привыкли думать, что это не означает тристо, четыре десятка и два, но вместо

три 64, четыре 8 и два 1 *

или

три 256, четыре 16 и 2 единицы

Это действительно то, что нужно сделать вашей воображаемой системе счисления, но каждая цифра - это основание длины этой соответствующей стороны в массиве, умноженное на следующее нижнее основание (если только его нет, в этом случае, 1. Последнеедлина массива не используется в этом вычислении, но вместо этого, только для ограничения вашего цикла. Порядок в этом расчете основан на том, как вы хотите преобразовать длины сторон в линейные элементы.

Для массива 5x5x5 это легко:

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

Другие базы могут быть более сложными, особенно с неоднородными размерами, но это просто еще один способ осмыслить проблему.

Вот неоднородный пример 565:

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

Answer 4

Вы можете по-разному отображать многомерные массивы в линейные. Дело в том, что вы должны выбрать соглашение. Пойдем со следующим соглашением. Первый индекс указывает контейнерный блок, второй - блок в одном из предыдущих контейнеров, и, наконец, третий индекс - это смещение внутри блока. Вы можете легко обобщить это для многомерности, но для этого примера оставим его равным 3:

#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 5

Вы можете сделать следующее в 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];
    }
}

Или преобразовать в n-мерный массив.

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

и проверить.

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