C语言高效实现向量循环移位

2020-01-06 20:15:53于海丽


/*LOOPSHIFT(V,i)*/
cnt←0
j←-1
while cnt≠length[V]
 do j←j+1
   temp←V[j]
   k←i+j
   while k%n≠j
    do V[(k-i)%n]←V[k%n]
     k←k+i
     cnt←cnt+1
   V[(k-i)%n]←temp
   cnt←cnt+1

在继续深入考虑之前先思考以下两种情况:①在13个元素中循环移动5个元素(12/5) ②在14个元素中移动4个元素(14/4),其中⌈⌉表示上取整,⌊⌋表示下取整。

1)在13/5这种情况中,由于(⌈12/5⌉)×5-12=3,每次在5个元素中以2进行循环迭代,在[0,4]这5个元素中的迭代次序为(不考虑向量中的其他元素):0→3→1(6%5)→4(9%5)→2(12%5)→0(15%5),因此最终通过上述代码的一次内层循环即可完成整个移位操作。

2)在14/4这种情况中,由于(⌈14/4⌉)×4-14=2,每次在4个元素中也以2进行循环迭代,在[0,3]这5个元素中的迭代次序为:0→2→0(4%2)→1(退出内层循环,简单从下标为1的元素重新开始移动)→3→1(5%2),因此最后在外层执行两次迭代才最终完成整个移位操作。

通过这两个例子可以发现外层的迭代次数(即等价类的个数)最终和整个向量的长度以及所要移位的个数有关,具体的关系为:cnt = gcd(n,i)  其中n=length[A],cnt为外层迭代的次数。

由于任何求模等价类聚集中每个集合中的元素间隔的长度相等(由上可知,即实际过程中未进行模运算之前的值),据此证明过程如下:

因为length[V]=n且移位个数为i,因此必然存在大于等于n且被i整除的数k=⌈n/i⌉×i

由n= α×gcd(n,i)且i=β×gcd(n,i),k=⌈n/i⌉×β×gcd(n,i)

因此在i个元素上每次移位的个数为iter=k-n=(⌈n/i⌉×β-α)×gcd(n,i),即iter能被gcd(n,i)整除