Вдохновленный Википедией - Следуя описанию алгоритма циклов , я придумал следующую реализацию C ++:
#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 из transpose представляет размер строки, размер столбца 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, в противном случае </p>
Мы можем выделить четыре цикла в этой последовательности: { 0 }, { 1, 2, 4 }, {3, 5, 6} и { 7 }.Каждый цикл может быть транспонирован независимо от других циклов.Переменная cycle изначально указывает на второй элемент (первый не нужно перемещать, потому что 0 → 0).Битовый массив visited содержит уже транспонированные элементы и указывает, что индекс 1 (второй элемент) необходимо переместить.Индекс 1 заменяется на индекс 2 (функция отображения).Теперь индекс 1 содержит элемент индекса 2, и этот элемент заменяется элементом индекса 4. Теперь индекс 1 содержит элемент индекса 4. Элемент индекса 4 должен перейти к индексу 1, он находится в нужном месте, транспонируяцикла завершены, все затронутые индексы были отмечены как посещенные.Переменная cycle увеличивается до первого не посещенного индекса, который равен 3. Процедура продолжается с этим циклом, пока все циклы не будут транспонированы.