编程小知识 之 序列 rotate
编程小知识 之 序列 rotate
本文简述了 序列 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 函数的第一个参数即是我们需要旋转的列表(即 lll),第二个参数 3 则是旋转的 offsetoffsetoffset,表示我们要旋转序列的前 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(n2)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)lll 中的元素顺序变为 {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 操作,原始索引 aaa 和变换后(revert 后)索引 a′a'a′ 存在以下关系:
a′=i+j−a a' = i + j - a a′=i+j−a
- 接着,我们可以证明,对于 序列 rotate 操作,旋转元素索引 aaa 的最终索引 a′a'a′ 和 剩余元素索引 bbb 的最终索引 b′b'b′ 存在以下关系(其中 nnn 为序列长度, offsetoffsetoffset 为旋转偏移):
a′=n−offset+ab′=−offset+b \begin{aligned} & a' = n - offset + a \\ & b' = -offset + b \end{aligned} a′=n−offset+ab′=−offset+b
- 最后,对于旋转元素索引 aaa,可以证明经过两步 序列 revert 后,可以正确变换为最终索引 a′a'a′(bbb 可以正确变换为 b′b'b′ 同证)：
t′=1+offset−a← ∵revert(list,1,offset)a′=1+n−t′← ∵revert(list,1,n) =1+n−1−offset+a =n−offset+a \begin{aligned} & t' = 1 + offset - a \leftarrow \space \because revert(list, 1, offset) \\ & a' = 1 + n - t' \leftarrow \space \because revert(list, 1, n) \\ &\ \ \ = 1 + n - 1 - offset + a \\ &\ \ \ = n - offset + a \end{aligned} t′=1+offset−a← ∵revert(list,1,offset)a′=1+n−t′← ∵revert(list,1,n) =1+n−1−offset+a =n−offset+a
除了上面这种实现方法,我们还可以使用递归的方法来实现 序列 rotate, 仍然考虑序列 l={1,2,3,4,5}l = \{ 1, 2, 3, 4, 5 \}l={1,2,3,4,5}, 我们要进行 offsetoffsetoffset 为 3 的旋转操作,我们首先将序列中的元素 2,32, 32,3 和元素 4,54, 54,5 交换位置,则原序列变为:
l={1,4,5,2,3}l = \{ 1, 4, 5, 2, 3 \}l={1,4,5,2,3}
此时, 元素 2,32, 32,3 已经在目标位置上了,此时我们要做的就是对 lll 进行一次更小范围的 rotate 操作(对元素 1,4,51, 4, 51,4,5 进行一次 offsetoffsetoffset 为 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