Python数组旋转

Question

所以我在python中实现了一个块交换算法.

我遵循的算法是这样的:

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

a)如果A较短,则将B分成B1和Br,使得Br与A的长度相同.交换A和Br以将ABlBr变为BrBlA.现在A处于最后的位置,因此重复出现在B.

b)如果A较长,则将A分成Al和Ar,使得Al与B交换Al和B的长度相同,以将AlArB变为BArAl.现在B处于最后的位置,因此重复出现在A.

2)最后,当A和B的大小相等时,阻止交换它们.

该网站上的C实现了相同的算法 - 阵列旋转

我的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 vs slices相反.

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

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版本(再次注意符号vs的差异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]))  

Answer 2

我发现了一个问题，我需要对 k 的大值进行左右旋转（其中 k 是旋转次数），因此，我为任意大小的 k 实现了以下函数。

右圆旋转（从左到右：1234 -> 4123）：

def right_rotation(a, k):
   # if the size of k > len(a), rotate only necessary with
   # module of the division
   rotations = k % len(a)
   return a[-rotations:] + a[:-rotations]

左圆周旋转（从右到左：1234 -> 2341）：

def left_rotation(a, k):
   # if the size of k > len(a), rotate only necessary with
   # module of the division
   rotations = k % len(a)
   return a[rotations:] + a[:rotations]

资料来源：

• /sf/answers/3279258111/
• /sf/answers/662054641/

Answer 3

python中数组旋转的smiple和简写语法是

arr = arr[numOfRotations:]+arr[:numOfRotations]

例:

arr = [1,2,3,4,5]
rotations = 4
then 

arr = arr[4:]+arr[:4]

给我们

[5,1,2,3,4]

Answer 4

你真的需要实现块交换还是只是想要旋转数组？在python中,你可以使用CW和CWW旋转

zip(*arr[::-1])

和

zip(*arr)[::-1]