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](http://www.geeksforgeeks.org/block-swap-algorithm-for-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: You can rotate a list in place in Python by using a
[deque](http://docs.python.org/2/library/collections.html#collections.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'
    

