17

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

我遵循的算法是这样的：

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

a) 如果 A 较短，则将 B 分为 Bl 和 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 语言实现了相同的算法 - 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)

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

4

11 回答 11

30

您可以使用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 版本（再次注意 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]))
于 2013-06-27T18:23:39.753 回答
16

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

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

例子：

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

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

给我们

[5,1,2,3,4]

于 2017-10-20T09:50:49.307 回答
9

我发现了一个问题，即对于较大的 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]

资料来源：

于 2018-09-02T16:39:51.423 回答
5

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

zip(*arr[::-1])

和

zip(*arr)[::-1]
于 2013-06-27T18:20:50.180 回答
1

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

例如考虑这个函数：

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

我刚刚尝试了以下方法：

>>> 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]

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

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

于 2013-06-27T18:25:19.077 回答
1

您可以使用此代码在 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]
于 2019-05-22T07:59:23.770 回答
0 
def rotate(nums=[1,2,3,4,5,6,7], k=3):
    i=0
    while i < k:
        pop_item = nums.pop()
        nums.insert(0, pop_item)
        i += 1

    return nums  # [5,6,7,1,2,3,4]
于 2021-09-06T19:24:22.927 回答
0 
def leftRotation():
    
    li = [int(x) for x in input().split()]

    d = int(input())
    ans = (li[d:]+li[0:d])

    for i in ans:
        print(i,end=' ')
    print()
    
leftRotation()
于 2020-10-15T15:20:11.237 回答
0

如果您不应该使用双端队列或切片：

def rotate(array: List[int], k: int) -> List[int]:
    # loop through the array from -k to array_size - k
    return [array[i] for i in range(-k, len(array) - k)]
于 2022-01-24T12:01:11.000 回答
0

阵列旋转：-

print("Right:1,Left:2")
op=int(input())
par=[1,2]
if op not in par:
   print("Invalid Input!!")
   
else:  
  arr=list(map(int,input().strip().split()))
  shift=int(input())
  if op ==1:
    right=arr[-shift:]+arr[:-shift]
    print(right)
  elif op==2:
    left=arr[shift:]+arr[:shift]  
    print(left)

输出：-`

Right:1,Left:2
1
12 45 78 91 72 64 62 43
2
[62, 43, 12, 45, 78, 91, 72, 64]`
于 2021-08-12T09:42:21.817 回答
0 
def rotLeft(a, d):
    lenght=len(a)
    for j in range(0,d):
     temp = a[0]
     
     for i in range(lenght-1):
        a[i] = a[i+1]
     a[lenght-1] = temp
    # Write your code here
    return a    
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    d = int(first_multiple_input[1])

    a = list(map(int, input().rstrip().split()))

    result = rotLeft(a, d)

    fptr.write(' '.join(map(str, result)))
    fptr.write('\n')

    fptr.close()
于 2021-05-10T13:09:59.647 回答