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.

Ingridingrim

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

Giffer

there are a lot of python i could use as you suggested. However it was given to me as a challenge that I had to implement without using the inhouse method. If you could suggest a modification in the above code, it would be great – Ingridingrim

@Giffer If li is a numpy.array, the addition does not concatenate both arrays but do an item by item addition instead. How can I do your rotate operation with a numpy array ? – Radioelement

@Giffer I like your answer a lot, I just wish I saw this answer earlier, in the meantime, I did this: np.concatenate((a[n:],a[:n])) – Radioelement

@Giffer According to IPython %timeit, np.concatenate( ( a[n:], a[:n] ) ) seems 10 times faster :) – Radioelement

@SebMa: np.concatenate( ( a[n:], a[:n] ) ) is indeed faster. It does slows down for larger arrays. Similar to the Python answer I gave I suppose. Thanks! I will add that. – Giffer

List slicing method will fail. When rotation value is more than the len of the list – Tartaglia

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]

Perth

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://mcmap.net/q/609888/-python-array-rotation
• https://mcmap.net/q/188418/-python-list-rotation-duplicate

Loralyn

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]

Forespeak

Can you explain this more? – See

@LongHoang This answer doesn't actually answer the question, as it does clockwise and counterclockwise rotations on 2D arrays. I will likely delete this answer later today. – Forespeak

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?

Pedo

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]

Cindy

@Ângelo Polotto's answer is correct, this one doesn't work at edge cases. – Iene

Answer 7

Array Rotation:-

print("Right:1,Left:2")
op=int(input())
par=[1,2]
if op not in par:
   print("Invalid Input!!")
   
else:  
  arr=list(map(int,input().strip().split()))
  shift=int(input())
  if op ==1:
    right=arr[-shift:]+arr[:-shift]
    print(right)
  elif op==2:
    left=arr[shift:]+arr[:shift]  
    print(left)

Ouput:-`

Right:1,Left:2
1
12 45 78 91 72 64 62 43
2
[62, 43, 12, 45, 78, 91, 72, 64]`

Fenton

Answer 8

If you are not supposed to use deque or slicing:

def rotate(array: List[int], k: int) -> List[int]:
    # loop through the array from -k to array_size - k
    return [array[i] for i in range(-k, len(array) - k)]

Thymelaeaceous

Answer 9

Here, I've used the method of swapping using a temporary variable to rotate an array. As an example, an array 'a' of size 5 is considered. Two variables 'j' and 'i' are used for outer and inner loop iterations respectively. 'c' is the temporary variable. Initially, the 1st element in the array is swapped with the last element in the array i.e a=[5,2,3,4,1]. Then, the 2nd element is swapped with the current last element i.e in this case 2 and 1. At present, the array 'a' would be a=[5,1,3,4,2]. This continues till it reaches the second last element in the array. Hence, if the size of the array is n (5 in this case), then n-1 iterations are done to rotate the array. To enter the no of times the rotation must be done, m is given a value with which the outer loop is run by comparing it with the value of j.

Note: The rotation of array is towards the left in this case

a=[1,2,3,4,5]
n=len(a)
m=int(input('Enter the no of rotations:'))
j=0
while(j<m):
    i=0
    while(i<n):
        c=a[i]
        a[i]=a[n-1]
        a[n-1]=c
        i=i+1
    j=j+1
print(a)

Enidenigma

Answer 10

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

Fresher

Could you explain what was wrong with the original code? – Pigment

There is nothing wrong with the original code. I just wanted to share a different approach where I used slicing. – Fresher

Answer 11

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

Scrappy

Answer 12

def rotate(nums=[1,2,3,4,5,6,7], k=3):
    i=0
    while i < k:
        pop_item = nums.pop()
        nums.insert(0, pop_item)
        i += 1

    return nums  # [5,6,7,1,2,3,4]

Nozicka

Welcome to StackOverflow. While this code may answer the question, providing additional context regarding how and/or why it solves the problem would improve the answer's long-term value. – Broz

Answer 13

def rotate(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: None Do not return anything, modify nums in-place instead.
    """
    result = []
    if len(nums) <= 1 : return nums
    if k > len(nums): k = K % len(nums)
    
    for i in range(k):
        result.insert(0,nums[-1])
        nums.pop()
    nums = result + nums
    return nums

Anissaanita

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Inwardness