Транспонирование матрицы - это просто
Интересная запись Два указателя в блоге AVVA напомнила мне проблему из моей далекой юности, тоже связанную с циклами:
Транспонировать прямоугольную матрицу m × n без дополнительной памяти (т.е. не используя память, размер которой зависит от размерности матрицы.)
Иначе говоря, в одномерном массиве размером m*n хранятся элементы матрицы, записанные построчно. Переставить их так, чтобы в этом же массиве получилась матрица, записанная поколонно.
Конечно, интерес представляет не тривиальный случай квадратной матрицы, а общий случай. Я умею это сделать простым алгоритмом квадратичной сложности. Существуют ли более эффективные алгоритмы, я не знаю.
Мне эта задачка представляется весьма интересной, и я написал о ней в комментарии к посту Аввы. Но она заинтересовала только одного читателя - bopstr - отчасти, наверное, потому, что я написал комментарий через пару дней после поста, когда, когда большинство читателей уже его посмотрели/прокомментировали. К тому же, на первый взгляд могло показаться, что это чистая задача на программирование. И она таки, действительно, когда-то выросла из программирования, но сейчас трудно представить себе ситуацию, когда нельзя было бы найти дополнительную память (ну хотя бы на диске) чтобы напрямую транспонировать матрицу их одного массива в другой.
Challenge возникает, когда требуется транспонировать матрицу, переставляя ее элементы в том же массиве. Для квадратной матрицы можно просто менять местами элементы, симметричные относительно диагонали. Но в случае НЕ квадратной матрицы возникают циклы длиной больше 2, с которыми нужно разобраться, чтобы никакие элементы не пропустить, но и не переставлять повторно.
Поначалу я пытался решить задачу алгебраически: зная размерность матрицы m × n найти формулу/алгоритм, который генерирует по одному представителю каждого цикла перестановки. Я безуспешно пытался построить такой генератор, обсуждал это с хорошими алгебраистами, но в конце концов вынужден был отказаться от этого подхода, и перешел к более общей проблеме, включающей транспонирование матрицы как частный случай.
А именно: Имеется последовательность N элементов A=(a1, a2, ..., aN), и функция f(k) , определяющая перестановку этой последовательности, т.е. биекция последовательности на себя. Построить алгоритм, реализующий эту биекцию без дополнительной памяти.
Для случая транстонирования матрицы: A=(a1, a2, ..., am*n) - это последовательность элементов матрицы, записанной построчно, а функция f(k), определяющая новую позицию элемента ak, имеет вид f(k) = (k%m)*n + k/m.
Теперь можно предложить простой (и довольно элегантный, на мой взгляд) алгоритм:
1. Пробегаем последовательно все k = 1, …, N-1.
2. Для каждого k сначала производим “dry run”, т.е. последовательно применяя функцию f() перебираем элементы цикла, которому принадлежит ak, но без перестановки элементов последовательности. Если идя по циклу встретим позицию p < k, значит этот цикл уже был пройден, и переходим к следующему элементу к+1.
Если же, пройдя весь цикл, возвращаемся к позиции k, это значит, что этот цикл встретился впервые. В этом случае проходим цикл еще раз, «повернув» его на один шаг, т.е сдвигаем каждый элемент цикла на следующую позицию.
Мы пообсуждали в блоге АВВЫ эту задачку с юзером bopstr, и он пришел к такому же алгоритму, и даже реализовал его в С++ программке.
Алгоритм, очевидно, квадратичный, что легко видно для случая последоватедьности A с единственным циклом (длины N). В случае же транспонирования матрицы, цикла длины N не бывает, т.к. первый и последний элементы матрицы всегда остаются на своих местах, но есть перестановки с циклом длины N-2. Я для фана тоже написал програмку транспонирования и прогнал ее до матриц размерности 200х200. При этом 965 матриц оказались с циклом длины N-2, - начиная с 2x3, 2x6, … и кончая 195x198. (При этом все вычисления заняли лишь несколько секунд.)
Транспонировать прямоугольную матрицу m × n без дополнительной памяти (т.е. не используя память, размер которой зависит от размерности матрицы.)
Иначе говоря, в одномерном массиве размером m*n хранятся элементы матрицы, записанные построчно. Переставить их так, чтобы в этом же массиве получилась матрица, записанная поколонно.
Конечно, интерес представляет не тривиальный случай квадратной матрицы, а общий случай. Я умею это сделать простым алгоритмом квадратичной сложности. Существуют ли более эффективные алгоритмы, я не знаю.
Мне эта задачка представляется весьма интересной, и я написал о ней в комментарии к посту Аввы. Но она заинтересовала только одного читателя - bopstr - отчасти, наверное, потому, что я написал комментарий через пару дней после поста, когда, когда большинство читателей уже его посмотрели/прокомментировали. К тому же, на первый взгляд могло показаться, что это чистая задача на программирование. И она таки, действительно, когда-то выросла из программирования, но сейчас трудно представить себе ситуацию, когда нельзя было бы найти дополнительную память (ну хотя бы на диске) чтобы напрямую транспонировать матрицу их одного массива в другой.
Challenge возникает, когда требуется транспонировать матрицу, переставляя ее элементы в том же массиве. Для квадратной матрицы можно просто менять местами элементы, симметричные относительно диагонали. Но в случае НЕ квадратной матрицы возникают циклы длиной больше 2, с которыми нужно разобраться, чтобы никакие элементы не пропустить, но и не переставлять повторно.
Поначалу я пытался решить задачу алгебраически: зная размерность матрицы m × n найти формулу/алгоритм, который генерирует по одному представителю каждого цикла перестановки. Я безуспешно пытался построить такой генератор, обсуждал это с хорошими алгебраистами, но в конце концов вынужден был отказаться от этого подхода, и перешел к более общей проблеме, включающей транспонирование матрицы как частный случай.
А именно: Имеется последовательность N элементов A=(a1, a2, ..., aN), и функция f(k) , определяющая перестановку этой последовательности, т.е. биекция последовательности на себя. Построить алгоритм, реализующий эту биекцию без дополнительной памяти.
Для случая транстонирования матрицы: A=(a1, a2, ..., am*n) - это последовательность элементов матрицы, записанной построчно, а функция f(k), определяющая новую позицию элемента ak, имеет вид f(k) = (k%m)*n + k/m.
Теперь можно предложить простой (и довольно элегантный, на мой взгляд) алгоритм:
1. Пробегаем последовательно все k = 1, …, N-1.
2. Для каждого k сначала производим “dry run”, т.е. последовательно применяя функцию f() перебираем элементы цикла, которому принадлежит ak, но без перестановки элементов последовательности. Если идя по циклу встретим позицию p < k, значит этот цикл уже был пройден, и переходим к следующему элементу к+1.
Если же, пройдя весь цикл, возвращаемся к позиции k, это значит, что этот цикл встретился впервые. В этом случае проходим цикл еще раз, «повернув» его на один шаг, т.е сдвигаем каждый элемент цикла на следующую позицию.
Мы пообсуждали в блоге АВВЫ эту задачку с юзером bopstr, и он пришел к такому же алгоритму, и даже реализовал его в С++ программке.
Алгоритм, очевидно, квадратичный, что легко видно для случая последоватедьности A с единственным циклом (длины N). В случае же транспонирования матрицы, цикла длины N не бывает, т.к. первый и последний элементы матрицы всегда остаются на своих местах, но есть перестановки с циклом длины N-2. Я для фана тоже написал програмку транспонирования и прогнал ее до матриц размерности 200х200. При этом 965 матриц оказались с циклом длины N-2, - начиная с 2x3, 2x6, … и кончая 195x198. (При этом все вычисления заняли лишь несколько секунд.)