Python Array Rotation

Question

Therefore, I implement a block exchange algorithm in Python.

The algorithm that I follow is this:

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

a) If A is shorter, divide B by Bl and Br so that Br is the same length as A. Swap A and Br to replace ABlBr with BrBlA. Now A is in its last place, so let's go back to pieces of B.

b) If A is longer, divide A by Al and Ar so that Al is the same length as B, swap Al and B to replace AlArB with BArAl. Now B is in its last place, so back to pieces A.

2) Finally, when A and B are the same size, the block swaps them.

The same algorithm was implemented in C on this site - Array Rotation

My Python code is for the same

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 < nx: 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[:nx],x) else: print(a) for i in range(nx): a[i], a[(i-(nx) + n) % n] = a[(i-(nx) + n) % n] , a[i] print(a) rotate(a[nx:], nx) rotate(a,x) print(a) 

I get the correct values ​​at each stage, but a recursive function call does not return the expected result, and I cannot understand the reason. Can someone explain what is wrong with my recursion? and what could be a possible alternative.

Answer 1

You can rotate the list in place in Python using 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 lists of lists:

 >>> 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 the opposite of deque.rotate vs slices.

If you want to use a function that has the same 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 the numpy version of the same rotate above (again, noting the difference in the vs np.roll sign):

 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

Simple and abbreviated syntax for rotating an array in 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]

Answer 3

Do you really need to implement block locking or do you just want to rotate the array? In python, you can do CW and CWW rotations with

 zip(*arr[::-1]) 

and

 zip(*arr)[::-1] 

Answer 4

I found a problem that required turning left and right for large k values ​​(where k is the number of turns), so I implemented the following functions for any size k.

Circular rotation to the right (from left to 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] 

Circular rotation to the left (from right to 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:

• fooobar.com/questions/1488560 / ...
• fooobar.com/questions/94236 / ...

Answer 5

I expect that when you pass fragment a to your recursive call, you no longer pass the same variable. Try passing in whole and the upper / lower bounds of your fragment as additional arguments to your function.

For example, 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] 

If you see that the slice modification was not saved in a full array

Out of curiosity, what results do you get and what do you expect?

Answer 6

You can use this code to rotate left in a Python array

 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]