Python Array Rotation

So I am implementing a block swap algorithm in 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) 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) 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) Finally when A and B are of equal size, block swap them.

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

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.

5 Answers
5

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

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

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

>>> 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 rotate above (again noting the difference in sign vs np.roll):

rotate

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


np.concatenate((a[n:],a[:n]))

np.concatenate( ( a[n:], a[:n] ) )

A smiple and shorthand syntax for array rotation in python is

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]

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

zip(*arr[::-1])


and

zip(*arr)[::-1]


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.

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?

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.

Right Circular Rotation (left to the right: 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):

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:

Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.