Транспонирование неквадратной матрицы на месте, представленной в виде линейного массива, немного
хитрости
Вот программа REXX, которая выполняет транспонирование на месте
2D матрица, представленная в одном
размерный массив размером M * N , где M - число
строки и
N - столбец в
нетранспонированный массив. После транспонирования M становится числом столбцов и
N становится числом строк.
i = 0 /* linear array index */
do j = 1 to N /* j = 1 to columns of non-transposed array */
do k = 1 to M /* k = 1 to rows of non-transposed array */
i = i + 1
t = (k - 1) * N + j
do while t < i
jp = (t - 1) % M + 1
kp = t - (jp - 1) * M
t = (kp - 1) * N + jp
end
if i \= t then say 'exchange('i',' t')' /* swap elements */
end
end
Приведенная выше программа отображает элементы массива, которые необходимо заменить, чтобы получить транспонированный массив.
Эта программа будет работать для любого
размерная матрица, представленная в виде линейного массива, в котором расположены элементы
по столбцу, затем по строке. Например, матрица M на N будет иметь следующие элементы:
X 1,1 , X 1,2 , ... X 1, N , X 2,1 , X 2,2 , ... X 2, N , ... X M, N
Программа выводит индексы линейного массива элементов, которые необходимо заменить, чтобы получить
транспонированная матрица вида:
X 1,1 , X 2,1 , ... X M, 1 , X 1,2 , Х 2,2 , ... Х М, 2 , ... Х М, N
Например, начать с M = 4, N = 2 и массива, содержащего:
A1, B1, A2, B2, A3, B3, A4, B4
Выполните следующие обмены:
exchange(2, 3)
exchange(3, 5)
exchange(4, 7)
exchange(6, 7)
и расположение становится:
A1, A2, A3, A4, B1, B2, B3, B4
Как это работает?
Начните с обозначения, чтобы идентифицировать каждый элемент в линейном массиве как:
X[i,j,k]
where: i is the linear array index for an element in X
j is the row number for element in X
k is the column number for element in X
Используя эту нотацию, массив в главном порядке строк может быть сгенерирован как:
i = 0
do j = 1 to M /* Row counter */
do k = 1 to N /* Column counter */
i = i + 1 /* array index of element j, k */
say 'X['i','j','k']'
end
end
Обратите внимание, что для значений j (строка) и k (столбец), i , индекс линейного массива для X i, j , можно рассчитать как:
i = (j - 1) * N + k
Транспонирование матрицы X создается путем замены элементов
X [i, j, k] с X [t, k, j] в диапазоне от j = 1 до M и k = От 1 до N при условии i> t . В
суть мы обмениваем все
переменные строки для переменных столбца. Используя обозначения, описанные выше, это составляет
для обмена элементами линейного массива:
exchange(X[i,j,k], X[t,k,j])
Учитывая значения для j и k , мы можем вычислить значения i и t как:
i = (j - 1) * N + k
t = (k - 1) * M + i
Теперь перейдите к линейному массиву, выполняя вышеуказанные обмены, когда i увеличено с 1 до M * N.
Обратите внимание, что после каждой итерации все элементы X , имеющие индекс, меньший или равный i , имеют
были транспонированы. Это
потому что каждая итерация завершается только тогда, когда правильный элемент был
обменены на X [i] .
Всякий раз, когда i> t , это означает, что предыдущий обмен имел место по индексу t . Элемент в t был
обменяется, как указано выше, помещая его в новую позицию t простое число . Учитывая
index t , мы можем вычислить главный индекс строки t prime , а также строку и
Номера столбцов связаны с ним следующим образом:
j простое число = (т - 1)% M + 1
k простое число = t - (j простое число - 1) * M
t простое число = (k простое число - 1) * N + j простое число
Опять же, если t prime меньше i , это означает, что этот элемент был заменен
тоже, и мы должны продолжать
с другим раундом расчетов. Установите t на расчетное t простое число и повторите. В конце концов, я будет
стать меньше t и обмен может быть сделан. В основном мы следуем за элементом через все его
предыдущие обмены, пока мы не найдем его в i или справа от i в линейном массиве.
Повторите этот цикл для каждого элемента в линейном массиве, и матрица будет транспонирована.