受Wikipedia - Following the cycles算法描述的启发,我设计了以下C++实现:
#include <iostream>
#include <iterator>
#include <algorithm>
#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
represented by the row-major ordering
{0, 4, 1, 5, 2, 6, 3, 7}
。
transpose
的参数
m
表示行数,列数
n
由行数和序列大小确定。该算法需要
m
×
n
位辅助存储来存储已交换元素的信息。序列的索引使用以下方案映射:
0 → 0
1 → 2
2 → 4
3 → 6
4 → 1
5 → 3
6 → 5
7 → 7
一般情况下,映射函数如下所示:
如果 idx < (m × n),则 idx → (idx × n) mod (m × n - 1);否则 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。该过程继续进行到所有循环都被转置为止。