本文简述了 序列 rotate 的一些知识

本篇文章中所说的 序列 rotate(旋转) 可能跟我们平常理解的 图像 rotate(旋转) 不太相同,所谓 序列 rotate,其实就是一种调整序列元素顺序的方法,而要理解这种方法之所以称为 rotate(旋转),我们需要将序列想象为一个环形结构,而 rotate 操作其实就是在这个环形结构上对序列进行旋转.

举个简单的例子,假设我们有序列 l = { 1 , 2 , 3 , 4 , 5 } l = \{ 1, 2, 3, 4, 5 \} l={1,2,3,4,5},我们对其执行 rotate 操作:

rotate(l, 3)

其中 rotate 函数的第一个参数即是我们需要旋转的列表(即 l l l),第二个参数 3 则是旋转的 o f f s e t offset offset,表示我们要旋转序列的前 3 个元素, rotate 之后的结果则为 l = { 4 , 5 , 1 , 2 , 3 } l = \{ 4, 5, 1, 2, 3 \} l={4,5,1,2,3}

下面的示意图展示了这个过程:

实现 rotate 的方法很多,比较简单的一种方法就是借助临时缓冲区:首先将需要旋转的序列元素拷贝至临时缓冲区,再将序列的剩余元素移动至序列前部,再将临时缓冲区的元素拷贝回来(至序列尾部)即可.

function rotate(list, offset)
    local buffer = {}
    
    for i = 1, offset do
        table.insert(buffer, list[i])
    end
    
    local index = 1
    
    for i = offset + 1, #list do
        list[index] = list[i]
        index = index + 1
    end
    
    for i = 1, #buffer do
        list[index] = buffer[i]
        index = index + 1
    end
end

当然,使用临时缓冲区实现 rotate 的方法还有很多,这些方法自然也都需要临时缓冲区的帮助,那有没有不使用临时缓冲区的实现方式呢?

最简单的一种(不使用临时缓冲区)实现方式就是将旋转元素依次移动至序列尾部,并整体前移其余的序列元素:

function rotate(list, offset)
    for i = 1, offset do
        local t = list[1]
        for j = 2, #list do
            list[j - 1] = list[j]
        end
        list[#list] = t
    end
end

上面这种实现方式的时间复杂度比较高(平均情况下为 O ( n 2 ) O(n^2) O(n2)),另一种技巧性比较强但时间复杂度比较低(为 O ( n ) O(n) O(n))的实现方式则是借助 序列 revert 来实现 序列 rotate.

所谓 序列 revert, 其实就是将序列的元素反序,还是拿之前 l = { 1 , 2 , 3 , 4 , 5 } l = \{ 1, 2, 3, 4, 5 \} l={1,2,3,4,5} 举例,经过 revert 操作之后(revert 函数的三个参数分别为: 操作列表, 起始索引 和 结束索引):

revert(l, 1, 5)

l l l 中的元素顺序变为 { 5 , 4 , 3 , 2 , 1 } \{ 5, 4, 3, 2, 1 \} {5,4,3,2,1}.

而要实现 序列 rotate, 我们仅需要对序列进行 3 次 revert 即可:

function rotate(list, offset)
    revert(list, 1, offset)
    revert(list, offset + 1, #list)
    revert(list, 1, #list)
end

对于这种实现方式,我个人觉得很难从直观上进行理解,所以我从数学证明的角度出发进行了一点验证:

• 首先,我们可以证明,在索引范围为 [ i , j ] [i, j] [i,j] 上执行 序列 revert 操作,原始索引 a a a 和变换后(revert 后)索引 a ′ a' a′ 存在以下关系:

a ′ = i + j − a a' = i + j - a a′=i+j−a

• 接着,我们可以证明,对于 序列 rotate 操作,旋转元素索引 a a a 的最终索引 a ′ a' a′ 和 剩余元素索引 b b b 的最终索引 b ′ b' b′ 存在以下关系(其中 n n n 为序列长度, o f f s e t offset offset 为旋转偏移):

a ′ = n − o f f s e t + a b ′ = − o f f s e t + b

​a′=n−offset+ab′=−offset+b​

• 最后,对于旋转元素索引 a a a,可以证明经过两步 序列 revert 后,可以正确变换为最终索引 a ′ a' a′( b b b 可以正确变换为 b ′ b' b′ 同证)：

t ′ = 1 + o f f s e t − a ←   ∵ r e v e r t ( l i s t , 1 , o f f s e t ) a ′ = 1 + n − t ′ ←   ∵ r e v e r t ( l i s t , 1 , n )     = 1 + n − 1 − o f f s e t + a     = n − o f f s e t + a

​t′=1+offset−a← ∵revert(list,1,offset)a′=1+n−t′← ∵revert(list,1,n)   =1+n−1−offset+a   =n−offset+a​

上面基于索引计算的验证方式比较繁琐,也不直观,更好的证明方式其实是对 r e v e r t revert revert 操作进行抽象:

我们将原始序列按照 r o t a t e rotate rotate 的旋转偏移分为两个子序列 A B AB AB,我们想做的就是通过 r e v e r t revert revert 操作把 A B AB AB 变换为 B A BA BA.

对于 r e v e r t revert revert 操作(以下简写为 r r r),我们有( S S S 代表序列):

r ( r ( S ) ) = S r ( S 1 S 2 ) = r ( S 2 ) r ( S 1 ) r(r(S)) = S \\ r(S_1S_2) = r(S_2)r(S_1) r(r(S))=Sr(S1​S2​)=r(S2​)r(S1​)

于是对于之前的目标序列 B A BA BA,我们有:

B A = r ( r ( B ) ) r ( r ( A ) ) = r ( r ( A ) r ( B ) ) BA = r(r(B))r(r(A)) = r(r(A)r(B)) BA=r(r(B))r(r(A))=r(r(A)r(B))

原命题即得证

---

除了上面这种实现方法,我们还可以使用递归的方法来实现 序列 rotate, 仍然考虑序列 l = { 1 , 2 , 3 , 4 , 5 } l = \{ 1, 2, 3, 4, 5 \} l={1,2,3,4,5}, 我们要进行 o f f s e t offset offset 为 3 的旋转操作,我们首先将序列中的元素 2 , 3 2, 3 2,3 和元素 4 , 5 4, 5 4,5 交换位置,则原序列变为:

l = { 1 , 4 , 5 , 2 , 3 } l = \{ 1, 4, 5, 2, 3 \} l={1,4,5,2,3}

此时, 元素 2 , 3 2, 3 2,3 已经在目标位置上了,此时我们要做的就是对 l l l 进行一次更小范围的 rotate 操作(对元素 1 , 4 , 5 1, 4, 5 1,4,5 进行一次 o f f s e t offset offset 为 1 的 rotate),依次类推,我们自然会得到 rotate 的递归实现(我们也可以将递归转为循环实现):

local function rotate_recur(list, start_index, end_index, offset_index)
    local left_count = offset_index - start_index + 1
    local right_count = end_index - offset_index
    if left_count <= 0 or right_count <= 0 or left_count + right_count <= 1 then
        -- do nothing
    elseif left_count == right_count then
        local index = start_index
        for i = 1, left_count do
            local t = list[index]
            list[index] = list[offset_index + i]
            list[offset_index + i] = t
            index = index + 1
        end
    elseif left_count < right_count then
        local index = start_index
        for i = 1, left_count do
            local t = list[index]
            list[index] = list[offset_index + i]
            list[offset_index + i] = t
            index = index + 1
        end
        rotate_recur(list, offset_index + 1, end_index, offset_index + left_count)
    else
        local index = end_index
        for i = 1, right_count do
            local t = list[index]
            list[index] = list[offset_index - i + 1]
            list[offset_index - i + 1] = t
            index = index - 1
        end
        rotate_recur(list, start_index, offset_index, offset_index - right_count)
    end
end

function rotate(list, offset)
    rotate_recur(list, 1, #list, offset)
end