Транзирование матрицы на месте

Ответ 1

Вдохновленный Википедия - После описания алгоритмов цикла, я придумал следующую реализацию на С++:

#include <iostream>  // std::cout
#include <iterator>  // std::ostream_iterator
#include <algorithm> // std::swap (until C++11)
#include <vector>

template<class RandomIterator>
void transpose(RandomIterator first, RandomIterator last, int m)
{
    const int mn1 = (last - first - 1);
    const int n   = (last - first) / m;
    std::vector<bool> visited(last - first);
    RandomIterator cycle = first;
    while (++cycle != last) {
        if (visited[cycle - first])
            continue;
        int a = cycle - first;
        do  {
            a = a == mn1 ? mn1 : (n * a) % mn1;
            std::swap(*(first + a), *cycle);
            visited[a] = true;
        } while ((first + a) != cycle);
    }
}

int main()
{
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
    transpose(a, a + 8, 4);
    std::copy(a, a + 8, std::ostream_iterator<int>(std::cout, " "));
}

Программа делает перенос матрицы на месте матрицы 2 × 4

0 1 2 3
4 5 6 7

представлен в упорядочивании строк {0, 1, 2, 3, 4, 5, 6, 7} в матрицу 4 × 2

0 4
1 5
2 6
3 7

представленное строковым упорядочением {0, 4, 1, 5, 2, 6, 3, 7}.

Аргумент m of transpose представляет строку rowize, columnize n определяется размером строки и размером последовательности. Алгоритм нуждается в битах m × n вспомогательной памяти для хранения информации, элементы которой были заменены. Индексы последовательности отображаются со следующей схемой:

0 → 0
1 → 2
2 → 4
3 → 6
4 → 1
5 → 3
6 → 5
7 → 7

Функция отображения в общем случае:

idx → (idx × n) mod (m × n - 1), если idx < (m × n), idx → idx в противном случае

В этой последовательности можно выделить четыре цикла: { 0 }, { 1, 2, 4 }, {3, 5, 6} и { 7 }. Каждый цикл может быть транспонирован независимо от других циклов. Переменная cycle изначально указывает на второй элемент (первый не нужно перемещать, потому что 0 → 0). Битовый массив visited содержит уже перенесенные элементы и указывает, что нужно переместить индекс 1 (второй элемент). Индекс 1 заменяется индексом 2 (функция отображения). Теперь индекс 1 содержит элемент индекса 2, и этот элемент обменивается с элементом индекса 4. Теперь индекс 1 содержит элемент индекса 4. Элемент индекса 4 должен перейти в индекс 1, он находится в нужном месте, транспонирование цикл завершен, все затронутые индексы отмечены посещением. Переменная cycle увеличивается до первого не посещаемого индекса, который равен 3. Процедура продолжается с этим циклом до тех пор, пока все циклы не будут транспонированы.

Ответ 2

Проблема заключается в том, что задача задана некорректно. Если бы вы имели в виду "одно и то же" использование одной и той же матрицы, это правильная задача. Но когда вы говорите о записи в одну и ту же область в памяти, "матрица представлена ​​как один массив размером m * n", вы должны добавить, как она представлена ​​там. В противном случае достаточно ничего изменить, кроме функции, которая читает эту матрицу - просто меняйте индексы в ней.

Вы хотите перенести представление матрицы в память так, чтобы функция чтения/установки для этой матрицы по индексам оставалась той же. Не так ли?

Кроме того, мы не можем записать алгоритм, не зная, является ли матрица, записанная в памяти по строкам или по столбцам. Хорошо, пусть написано строками. Не правда ли?

Если мы установим эти два недостающих условия, задача станет правильной и не составит труда решить.

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

Начальная матрица A:
  m - количество строк
  n - количество столбцов
  нм - количество элементов
  li - линейный индекс
  i - номер столбца
  j - номер строки

результирующая матрица B:
  lir - результат линейного индекса

Преобразование массива trans

//preparation
for (li=0;li<nm;li++){
    j=li / n;
    i=li-j*n;
    lir=i*m+j;
    trans[li]=lir;
}

// transposition
for (li=0;li<nm;li++){
   cur=li;
   lir=trans[cur];
   temp2=a[lir];
   cur=lir;
   while (cur!=li){
      lir=trans[cur];
      temp1=a[cur];
      a[cur]=temp2;
      temp2=temp1;
      check[cur]=1;
      cur=lir;
   }
}

Такая автоматическая транспозиция имеет смысл только в том случае, если в ячейках имеются тяжелые элементы.

В качестве функции можно реализовать trans [] array.

Ответ 3

Выполнение этого в общем случае требует определенных усилий. Неквадратные и внеаудиторные алгоритмы различаются. Сэкономьте себе много усилий и просто используйте FFTW. Я ранее подготовил более полную запись, включая пример кода, по этому вопросу.