Python Array Rotation

Question

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.

Answer 1

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

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

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

Answer 3

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:

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

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

Answer 5

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?

Answer 6

you can use this code for left rotation in 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]

Answer 7

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

Answer 8

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