Как преобразовать M-мерный массив в N-мерный массив?

Question

Вдохновленный arr2D[i][j] и arr1D[i * k + j], я хотел бы знать алгоритм, который может изменять размеры любого массива.

Позвольте мне попытаться формализовать его:

Ввод:

1. M Размерный контейнер A

2. Размеры D контейнера (размер)

3. Целевой размер N

Выход:

Если N > 0, тогда верните N-мерный контейнер B с тем же содержимым, что и A, чтобы в противном случае вернуть код ошибки.

Примечание:

Вы можете выбрать любой оптимальный размер для N-мерного контейнера.

Я бы лучше понимал код C ++ или C, чем алгоритм или код на каком-либо другом языке. Но вы можете помочь моему любопытству на любом языке, если это понятно на английском языке sh: P

Редактировать:

Мне не нужно работать полностью код. Я просто прошу пути решения этой проблемы. Заранее благодарим за любые хорошие идеи.

Answer 1

Итак, вы просто хотите переформатировать свои матрицы, пока данные не изменяются. Как я уже упоминал в своем комментарии, самое простое - использовать промежуточный массив 1D для преобразования из M в N измерений.

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

Для преобразования между A[A0][A1]...[A(M-1)] и X[A0*A1*...*A(M-1)], где A0,A1,...A(M-1) - это размеры вашего контейнера (разрешение), просто сделайте это:

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

, где a0,a1,...a(M-1) и x - индексы в массивах.

На самом деле вам не нужно преобразовывать массив MD в 1D, а затем обратно в ND, этого достаточно, чтобы просто преобразовать индексы так:

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

Не забывайте, что размеры должны быть:

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

в противном случае вы получите доступ к массиву за его пределами, так как данные в A не поместятся в B.

Если вы получили размерность динамического c, вы можете использовать :

• динамически вложенный для l oop nested_for

Answer 2

Ваш оригинальный M -мерный контейнер A.

Мы хотим создать новый N -мерный контейнер B, который будет содержать все содержимое A.

Сначала мы должны выяснить отображение, в котором мы можем легко найти один и тот же элемент в A и в B.

Давайте рассмотрим несколько примеров, чтобы определить, каким может быть отображение:

(1) М = 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) М = 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) М = 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) М = 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]

---

Если A имеет M измерений a1, a2, ..., aM и B имеет N измерений b1, b2, ..., bN, мы можем сказать, что:

, если M> N, то для всех 0

Таким образом, мы знаем, как создать B и Размер каждого измерения этого.

С помощью функции отображения, показанной в примерах, вы можете легко преобразовать любую матрицу M в матрицу N.

Если M < N, вы можете выполнить то же самое, но в противоположном направлении.

Answer 3

Поскольку вам не нужен код, позвольте мне объяснить, как вы можете сделать это с помощью шаблонов.

Допустим, у вас есть D-мерный массив размером n_ {0}, ..., n_ { d-1} вы всегда можете удалить одно измерение, объединив два из них, умножив размеры. Примеры: a [5] [4] [3] содержит 60 элементов, таким образом, b [20] [3] или c [5] [12] (для простых случаев, потому что вы можете даже построить d [15] [4] и любые перестановки) могут легко содержать те же элементы, что и a, отображение индексов также настолько очевидно ...

Теперь, используя C ++, сделать это намного сложнее, но вам понадобятся: variadi c шаблоны и шаблоны metaprogramming.

Variadi c шаблон для определения типа массива любого измерения, которое вы хотите, и шаблон метапрограммирования для определения оператора для преобразования D-мерного массива в N-мерный. (Я могу сказать, что это будет непросто, но очень сложное упражнение в метапрограммировании шаблонов).

Answer 4

Преобразует [100] в [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;
}