神奇的 排列循环算法

落雨晴天

看书看到一个很神奇的东西

排列循环算法

向后循环换位算法  执行数组元素的一个重新排列
因此向后循环换位对应于n个元素的一个置换

循环置换分解定理:对于给定数组a[0:n-1]向后循环换位n－k位运算，可分解为恰好gcd(k,n-k)个循环置换，且0，。。，gcd(k,n-k)-1中每个数恰好属于一个循环置换。其中gcd(x,n-k)表示整数x和y的最大公约数

数组块换位算法：

1. template <class T>
   
2. 
   
3. void exch(T a[],int n,int k)
   
4. 
   
5. {
   
6. 
   
7.    for(int i=0,cyc=gcd(k,n-k);i<cyc;i++){
   
8. 
   
9.         T tmp=a [ i];
   
10. 
    
11.         int p=i,j=(k+i)%n;
    
12. 
    
13.         while(j!=i){ a[p]=a[ j]; p=j; j=(k+p)%n;}
    
14. 
    
15.          a[p]=tmp;
    
16. 
    
17.          }
    
18. 
    
19. }

复制代码

移动元素次数n＋gcd(k,n-k)次

    换位数组块相等就简单了