向量旋转

 

本文先发布于：http://coderbee.net/index.php/algorithm/20130619/224

 

向量旋转

题目均来自《编程珠玑》，代码实现是用Go语言。

 

题

将一个n元一维向量向左旋转（循环移位）i个位置。例如，当n=8时且i=3时，向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。能否仅用数十个额外直接的存储空间，在正比于n的时间内完成向量的旋转？

 

旋转操作对应于交换相邻的不同大小的内存块：每当拖动文件中的一块文件到其他地方时，就要求程序交换两块内存中的内容。

 

两个简单直接的方法

方法一：首先将 x 的前 i 个元素复制到一个临时数组中，然后将余下的 n-i 个元素向左移动 i 个位置，最好将最初的 i 个元素从临时数组中复制到 x 中余下的位置。这种办法使用 i 个额外的位置产生了过大的存储空间的消耗。

 

方法二：定义一个函数将 i 向左旋转一个位置（其时间正比于 n），然后调用该函数 i 次。该方法产生了过多的运行时间消耗。

 

下面介绍三种更好的方法。

 

跳跃交换实现

这个算法的思路就是：向量旋转后，vec[i]存储的将是vec[2i]的值，vec[2i]存储的是vec[3i]的值，如此类推。

 

要注意的就是，如果 n % i != 0，那么，要移动的部分超出 n%i 的长部分位于 i - n%i 的后面，本来应该在前的，所以又需要对这一部分进行旋转。

 

实现

func VectorRotateByMagic(vec []byte, n int) {
    need, n := checkParam(vec, n)
    if !need {
        return
    }

    length := len(vec)
    for i := 0; i < n; i++ {
        v, j := vec[i], i+n
        for ; j < length; j += n {
            vec[j-n] = vec[j]
        }
        vec[j-n] = v
    }

    mod := length % n
    if mod != 0 {
        VectorRotateByMagic(vec[length-n:], n-mod)
    }
}

func checkParam(vec []byte, n int) (bool, int) {
    length := len(vec)
    if length < 2 {
        return false, n
    }

    if n < 0 {
        n = -1 * n
        n = n % length
        n = length - n
    } else {

        n = n % length
    }

    if n == 0 {
        return false, n
    }

    return true, n
}

 

用求逆实现

下面这张图足以说明这个算法的思路来了：

 

 

实现

func VectorRotateWithReverse(vec []byte, n int) {
    need, n := checkParam(vec, n)
    if !need {
        return
    }

    util.Reverse(vec[0:n])
    util.Reverse(vec[n:])
    util.Reverse(vec)
}

// util.Reverse
func Reverse(arr []byte) {
        var b byte
        for l, r := 0, len(arr)-1; l < r; l, r = l+1, r-1 {
            b = arr[l]
            arr[l] = arr[r]
            arr[r] = b
        }
}

 

用交换向量实现

原理：旋转向量x其实就是交换向量ab的两段，得到向量ba。 这里的a代表x中的前i个元素。假设a比b短，将b分为bL和bR，使得bR具有与a相同的长度。 交换a和bR，也就将a bL bR转换为bR bL a。序列a此时已处于其最终位置，因此现在的同样问题就集中到交换b的两部分。 由于新问题与原来的问题具有相同的形式，可以递归地解决。

 

实现

func VectorRotate(vec []byte, n int) {
    need, n := checkParam(vec, n)
    if !need {
        return
    }

    rotate(vec, n)
}

func rotate(vec []byte, l int) {
    length := len(vec)
    if length < 2 {
        return
    }

    r := length - l

    if l <= r {
        swapChunk(vec, 0, vec, length-l, l)
        rotate(vec[0:length-l], l)
    } else {
        swapChunk(vec, 0, vec, length-r, r)
        rotate(vec[r:], l-r)
    }
}

func swapChunk(src []byte, srcIndex int, dst []byte, dstIndex int, length int) {
    for i := 0; i < length; i, srcIndex, dstIndex = i+1, srcIndex+1, dstIndex+1 {
        t := src[srcIndex]
        src[srcIndex] = dst[dstIndex]
        dst[dstIndex] = t
    }
}

func checkParam(vec []byte, n int) (bool, int) {
    length := len(vec)
    if length < 2 {
        return false, n
    }

    if n < 0 {
        n = -1 * n
        n = n % length
        n = length - n
    } else {

        n = n % length
    }

    if n == 0 {
        return false, n
    }

    return true, n
}

问题扩展

向量旋转函数将向量ab变为ba。如何将向量abc变为cba？（这对交换非相邻内存块的问题进行建模）

 

这个问题其实可以先把 bc看作一个整体，那么问题就变为向量旋转的问题，旋转后变为bca，再对bc部分进行旋转，仍然是个向量旋转问题，旋转后即可得到最终结果cba。

 

如果用求逆的思路，仍然跟上面的类似。