Python 数组旋转

Question

所以我在 python 中实现了 block 交换算法。

我遵循的算法是这样的:

初始化 A = arr[0..d-1] 和 B = arr[d..n-1] 1) 执行以下操作直到 A 的大小等于 B 的大小

a) 如果 A 较短，则将 B 分成 Bl 和 Br 使得 Br 相同 长度为 A。交换 A 和 Br 将 ABlBr 变为 BrBlA。现在一个 在它的最终位置，所以在 B 的片段上重复。

b) 如果 A 较长，将 A 分成 Al 和 Ar，使得 Al 相同 Length as B 交换 Al 和 B 以将 AlArB 变为 BArAl。现在乙 在它的最终位置，所以重复 A 的片段。

2) 最后当 A 和 B 大小相等时， block 交换它们。

相同的算法已在本网站上用 C 实现 - Array Rotation

我的 python 代码是

a = [1,2,3,4,5,6,7,8]

x = 2

n = len(a)


def rotate(a,x):
    n = len(a)

    if x == 0 or x == n:
        return a

    if x == n -x:
        print(a)
        for i in range(x):
            a[i], a[(i-x+n) % n] = a[(i-x+n) % n], a[i]
        print(a)
        return a

    if x < n-x:
        print(a)
        for i in range(x):
            a[i], a[(i-x+n) % n] = a[(i-x+n) % n], a[i]
        print(a)
        rotate(a[:n-x],x)
    else:
        print(a)
        for i in range(n-x):
            a[i], a[(i-(n-x) + n) % n] = a[(i-(n-x) + n) % n] , a[i]
        print(a)
        rotate(a[n-x:], n-x)

rotate(a,x)
print(a)

我在每个阶段都得到了正确的值，但是递归函数调用没有返回预期的结果，我似乎无法理解原因。有人可以解释我的递归有什么问题吗？以及可能的替代方案是什么。

Answer 1

您可以使用 deque 在 Python 中就地旋转列表:

>>> from collections import deque
>>> d=deque([1,2,3,4,5])
>>> d
deque([1, 2, 3, 4, 5])
>>> d.rotate(2)
>>> d
deque([4, 5, 1, 2, 3])
>>> d.rotate(-2)
>>> d
deque([1, 2, 3, 4, 5])

或者用列表切片:

>>> li=[1,2,3,4,5]
>>> li[2:]+li[:2]
[3, 4, 5, 1, 2]
>>> li[-2:]+li[:-2]
[4, 5, 1, 2, 3]

请注意，符号约定与 deque.rotate 和切片相反。

如果您想要一个具有相同符号约定的函数:

def rotate(l, y=1):
   if len(l) == 0:
      return l
   y = -y % len(l)     # flip rotation direction
   return l[y:] + l[:y]

>>> rotate([1,2,3,4,5],2)
[4, 5, 1, 2, 3]
>>> rotate([1,2,3,4,5],-22)
[3, 4, 5, 1, 2]
>>> rotate('abcdefg',3)
'efgabcd'

---

对于 numpy，只需使用 np.roll

>>> a
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> np.roll(a, 1)
array([9, 0, 1, 2, 3, 4, 5, 6, 7, 8])
>>> np.roll(a, -1)
array([1, 2, 3, 4, 5, 6, 7, 8, 9, 0])

或者您可以使用上面相同的 rotate 的 numpy 版本(再次注意符号与 np.roll 的区别):

def rotate(a,n=1):
    if len(a) == 0:
        return a
    n = -n % len(a)     # flip rotation direction
    return np.concatenate((a[n:],a[:n]))