神奇的 排列循环算法
看书看到一个很神奇的东西排列循环算法
向后循环换位算法执行数组元素的一个重新排列
因此向后循环换位对应于n个元素的一个置换
循环置换分解定理:对于给定数组a向后循环换位n－k位运算，可分解为恰好gcd(k,n-k)个循环置换，且0，。。，gcd(k,n-k)-1中每个数恰好属于一个循环置换。其中gcd(x,n-k)表示整数x和y的最大公约数
数组块换位算法：
template <class T>
void exch(T a[],int n,int k)
{
for(int i=0,cyc=gcd(k,n-k);i<cyc;i++){
T tmp=a [ i];
int p=i,j=(k+i)%n;
while(j!=i){ a=a[ j]; p=j; j=(k+p)%n;}
a=tmp;
}
}
移动元素次数n＋gcd(k,n-k)次
换位数组块相等就简单了
页:
[1]