Python 数组旋转

Python Array Rotation

提问by Samarth

So I am implementing a block swap algorithm in python.

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

The algorithm I am following is this:

我遵循的算法是这样的：

Initialize A = arr[0..d-1] and B = arr[d..n-1] 1) Do following until size of A is equal to size of B

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

a) If A is shorter, divide B into Bl and Br such that Br is of same length as A. Swap A and Br to change ABlBr into BrBlA. Now A is at its final place, so recur on pieces of B.

a) 如果 A 较短，则将 B 分成 Bl 和 Br，使得 Br 与 A 的长度相同。交换 A 和 Br，将 ABlBr 变成 BrBlA。现在 A 处于最终位置，因此在 B 的各个部分上重复。

b) If A is longer, divide A into Al and Ar such that Al is of same length as B Swap Al and B to change AlArB into BArAl. Now B is at its final place, so recur on pieces of A.

b) 如果 A 较长，则将 A 分成 Al 和 Ar，使得 Al 与 B 的长度相同。 交换 Al 和 B，将 AlArB 变为 BArAl。现在 B 在它的最后位置，所以在 A 的碎片上重复。

2) Finally when A and B are of equal size, block swap them.

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

The same algorithm has been implemented in C on this website - Array Rotation

在这个网站上用 C 语言实现了相同的算法 - Array Rotation

My python code for the same is

我的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)

I am getting the right values at each stage but the recursive function call is not returning the expected result and I cannot seem to understand the cause. Can someone explain whats wrong with my recursion ? and what can be the possible alternative.

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

回答by wflynny

Do you actually need to implement the block swap or are you just looking to rotate the array? In python you can do CW and CWW rotations using

你真的需要实现块交换还是你只是想旋转阵列？在 python 中，您可以使用 CW 和 CWW 旋转

zip(*arr[::-1])

and

和

zip(*arr)[::-1]

回答by dawg

You can rotate a list in place in Python by using a deque:

您可以使用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])

Or with list slices:

或者使用列表切片：

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

Note that the sign convention is opposite with deque.rotate vs slices.

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

If you want a function that has the same sign convention:

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

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'

---

---

For numpy, just use np.roll

对于 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])

Or you can use a numpy version of the same rotateabove (again noting the difference in sign vs np.roll):

或者你可以使用rotate上面相同的 numpy 版本（再次注意 sign 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]))  

回答by user1245262

I expect that when you pass a slice of a to your recursive call, you're not passing the same variable any more. Try passing a in its entirety and the upper / lower bounds of your slice as additional arguments to your function.

我希望当您将 a 的一部分传递给您的递归调用时，您不再传递相同的变量。尝试将整个 a 和切片的上限/下限作为附加参数传递给您的函数。

For instance consider this function:

例如考虑这个函数：

def silly(z):
  z[0] = 2

I just tried the following:

我只是尝试了以下方法：

>>> z = [9,9,9,9,9,9]
>>> silly(z)
>>> z
[2, 9, 9, 9, 9, 9]
>>> silly(z[3:])
>>> z
[2, 9, 9, 9, 9, 9]

Where you can see the modification to the slice was not retained by the full array

您可以在哪里看到对切片的修改未被完整数组保留

Out of curiosity, what outputs do you get & what outputs do you expect?

出于好奇，您得到什么输出以及您期望什么输出？

回答by Yashwanth Chowdary Kata

A simple and shorthand syntax for array rotation in Python is

Python 中数组旋转的简单快捷语法是

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

Example:

例子：

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

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

gives us

给我们

[5,1,2,3,4]

[5,1,2,3,4]

回答by ?ngelo Polotto

I found a problem that I needed Right and Left rotations for big values of k (where k is number of rotations), so, I implemented the following functions for any size of k.

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

Right Circular Rotation(left to the right: 1234 -> 4123):

右圆周旋转（从左到右：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]

Left Circular Rotation(right to the left: 1234 -> 2341):

左圆周旋转（从右到左：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]

Sources:

资料来源：

• https://stackoverflow.com/a/46846544/7468664
• https://stackoverflow.com/a/9457923/7468664

• https://stackoverflow.com/a/46846544/7468664
• https://stackoverflow.com/a/9457923/7468664

回答by a.patidar

you can use this code for left rotation in python array

您可以使用此代码在 python 数组中进行左旋转

import copy
def leftRotate(arr,n) :
    _arr = copy.deepcopy(arr)
    for i in range(len(arr)-n):
        arr[i] = arr[i+n]
    for j in range(n):
        arr[(len(arr)-n)+j] = _arr[j]

arr = [1, 2, 3, 4, 5, 6, 7] 
leftRotateby = 3
leftRotate(arr,leftRotateby)
print arr 
#output:: [4, 5, 6, 7, 1, 2, 3]