1

For a given array I want to perform a number of right circular rotations. For instance given array [1, 2, 3] and number of rotation as 2, I want to obtain [2, 3, 1].

For that I have written the a code in Python given below. I have also looked into the solution given in here. However I am looking for an elegant algorithm that can perform it more efficiently using native data structure in Python.

Here is my code:

def circularArrayRotation(a, k):
    for i in range(k):
        temp = [0]*len(a)
        for j in range(len(a)-1):
            temp[j+1] = a[j]
        temp[0] = a[len(a)-1]
        a = temp
a = [1,2,3]
k = 2
Improve this question
1
  • 2
    Have you seen deque from the collections module? Commented Feb 3, 2019 at 6:52

3 Answers 3

Reset to default
3

You can use this trick : 

l = [1, 2, 3]
number_of_rotations = int(input())
number_of_rotations = number_of_rotations % len(l) 

rotated = l[number_of_rotations-1:] + l[:number_of_rotations-1]
print(rotated)

Look at the trick at line 3. If we rotate a list by its length number of times then we will get the original list back. That's why we don't need to do that. We will rotate that times which will actually effect.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

this is a great answer :) it could be better maybe using itertools.islice and itertools.cycle ... maybe
2

Use islice and cycle from itertools module:

from itertools import islice, cycle

lst = [1, 2, 3]

def rotate(lst, n):
    return list(islice(cycle(lst[::-1]), n, len(lst)+n))

Usage:

>>> rotate(lst, 2)[::-1]
[2, 3, 1]

Alternatively, use deque from collections module:

from collections import deque

lst = deque([1, 2, 3])
lst.rotate(2)

print(lst)
# [2, 3, 1]
Improve this answer

1 Comment

I agree ... but i think you need to reverse lst, and then unreverse it after the slice .... in order to get OP's output ... also you should take advantage of the modulo trick to not have to walk 300 rotations through a 3 item list
1

You could use a recursive appraoch:

def circularArrayRotation(a, k):
    if k == 0 or len(a) == 0: 
      return a
    return circularArrayRotation([a[-1]]+a[:-1], k-1)  

print(circularArrayRotation([1, 2, 3], 2))

Output:

[2, 3, 1]

The basic idea behind this is as follows. If you let the function circularArrayRotation be f then our function follows the following steps:

f([1, 2, 3], 2) = f([3] + [1, 2], 1) = f([3, 1, 2], 1)

f([3, 1, 2], 1) = f([2, 3, 1, 0) --> [3, 4, 1, 2] // we return the array instead of another function call as k == 0 (our base case)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.