Транспонирование матрицы - это просто

[dvornikstepanof]

Интересная запись Два указателя в блоге AVVA напомнила мне проблему из моей далекой юности, тоже связанную с циклами:
Транспонировать прямоугольную матрицу m × n без дополнительной памяти (т.е. не используя память, размер которой зависит от размерности матрицы.)
Иначе говоря, в одномерном массиве размером m*n хранятся элементы матрицы, записанные

Comments

[ext_3948950]

Извините, что выпал там из беседы - я почему-то не увидел уведомление о вашем ответе.

По поводу транспонирования матрицы. Довольно простой алгоритм позволяет транспонировать матрицу NxM за время O((N+M)^2) (и я совершенно не уверен, что знаю лучший). В случае узкой и длинной матрицы - это всё ещё квадратичная штука, но для матрицы, которая ближе к квадратной - линейная. Я ограничусь случаем, когда N и M взаимно простые - общий случай сводится к этому с помощью некоторых хаков. Вот как это делается. Для начала, менее эффективный алгоритм:

1) В каждой строке переставляем элементы так, чтобы элемент с номером i перешёл на место с номером (i*N) mod M. На каждую строку уходит время M^2 (так как биекция на себя), всего строк N, так что общее время N*M^2 (я предупреждал, это пока не так эффективно). Пример: матрица ABCDE/OPQRS/VWXYZ (то есть, 3x5) становится ACEBD/OQSPR/VXZWY.

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

[dvornikstepanof]

Спасибо за такой развернутый комментарий. Writing it was a lot of work, I guess. Попробую разобраться, как это работает.
На первый взгляд алгоритм выглядит несколько искусственным, и не сразу понятно, почему набор таких затейливых манипуляций в общем случае должен привести к правильному результату.
Мне также интересно, что подвигнуло автора алгоритма (Вас?) настолько серьезно заняться этой проблемой, учитывая, что практическая ценность такого алгоритма в наше время вряд ли велика. Разве что это implementation какого-то общего метода из Matrix Analysis или там Matrix Сomputation (от которых я давно очень далек, и нырять в их бездонные глубины нет достаточного стимула). Мне эта задача была интересна, и вспомнилась, как раз из-за ее «олимпиадности» - у нее простая постановка и простое но неочевидное решение.
Anyway, thanks for the enlightening comment.

[ext_3948950]

Всегда пожалуйста.

Почему работает. Представьте себе, что матрица свёрнута в бублик: правый край прилеплен к левому, а верхний - к нижнему. Тогда после первых двух шагов необходимая последовательность (AOVBPWCQXDRYESZ) будет идти по этому бублику по прямой - начиная с диагонали от левого верхнего угла. Именно поэтому элемент 1 в строке 0 переезжает в позицию N в той же строке: чтобы после того, как диагональ доберётся до нижнего края (позиции N-1 в строке N-1) и перескочит наверх, она попала бы точно в нужное место.

[dvornikstepanof]

Да, свернуть матрицу в тор - красивая идея.
Я поначалу, помнится, пробовал решать это как головоломку "15", но получалось как-то неуклюже. Деталей уже не помню, давно это было.

Re: Кстати дворник Степанов от Пиросмани

[dvornikstepanof]

Comment от trim_c не относится к теме поста. Я его перенес в архив, вместе со своим ответом.