Python阵列旋转 [英] Python Array Rotation

问题描述

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

So I am implementing a block swap algorithm in python.

我要遵循的算法是这样:

The algorithm I am following is this:

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

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)如果A较短，则将B分为Bl和Br，以使Br相同 交换A和Br以将ABlBr更改为BrBlA.现在一个 已经到了最后的位置，所以重复使用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.

b)如果A较长，则将A分为Al和Ar，以使Al相同 将长度替换为B交换Al和B，将AlArB转换为BArAl.现在B 处于最后位置，因此重复使用A.

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.

2)最后，当A和B的大小相等时，将它们交换交换.

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

该网站上的C语言也实现了相同的算法- Array旋转

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

我的python代码是

My python code for the same is

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.

推荐答案

您可以使用或带有列表切片:

>>> 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相反.

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

如果要使用具有相同符号约定的函数:

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'

---

对于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的区别):

Or you can use a numpy version of the same rotate above (again noting the difference in 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]))  

这篇关于Python阵列旋转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！