Python implementation of a cyclic vector rotation

Question

I am given a list a = [1, 0, 0, 1, 0]

What I want to do now is to define a function that takes as input a list a and s, where s is the number of positions I want to shift every entry of the list to the right. The rightmost entry will be shifted to the beginning of the list.

This means, the function shift(a, 2) should return r = [1, 0, 1, 0, 0]

I am given a solution, which I do not understand:

def shift(a, s):
    r = []
    for i in range(len(a)):
        r.append(a[(i-s) % len(a)])
    return r

First question: Although we are shifting to the right, we are subtracting the number of shifts s.

Second question: What is the purpose of the modulo operator?

Can somebody pls explain this to me at beginners level?

modulo operator provides that index would be in range i.e. it prevents list index out of range error — Daweo, Jan 08 '19 at 20:11
modulo operator gives you the remainder when dividing (i-s) by len(a). For example 3%5 = 3, 6%5 = 1, 12%5 = 2, 123%120 = 3 and so on. Now the purpose is explained in the above comment — Sheldore, Jan 08 '19 at 20:14
I'd suggest you take a pen and paper and do a simple dry run of the code snippet with a few examples. — Diptangsu Goswami, Jan 08 '19 at 20:15
These comments aren't completely accurate. In the for loop, `i-s` will never exceed `len(a)`. Instead, it takes negative values to their corresponding modulo. — Calvin Godfrey, Jan 08 '19 at 20:16

score 0 · Answer 1 · answered Jan 08 '19 at 20:15

What the modulo operator does is make sure all of the indices you try to access are in the range of the array. So in your example, s=2 and a=[1, 0, 0, 1, 0]. So going through thefor` loop step by step:

r.append(a[(0-2) % len(a)])
r.append(a[(1-2) % len(a)])
...
r.append(a[(4-2) % len(a)])

In the example, len(a)=5. In the first line, it evaluates to r.append(a[-2 % 5]), which, if you evaluate, is 3. So it first appends a[3] to r, which is 1.

In the next step, it evaluates to r.append(a[-1 % 5]), which is 4, and so a[4] gets appended.

Then in the next step, it becomes r.append(a[0 % 5]), which is just a[0]. And from then on, the modulo operator doesn't do anything, and it behaves just like you expect it would.

Thx, Calvin! It is interesting to see python deals with negative numbers in modulo different than C does — Luk, Jan 08 '19 at 21:02

score 0 · Accepted Answer · answered Jan 08 '19 at 20:16

Since you wanted an explanation to the solution already provided, I've commented below. The hardest part is the modulo, which you may want to read about how python handles running the modulo operation on a negative number (link)

def shift(a, s):
    # Initialize an empty list to be the result
    r = []
    # Iterate through the list by index
    for i in range(len(a)):
        # i - s will give you a positive number or a negative number
        # if negative, running modulo will do a true-modulo to give the correct index. Not very readable in my opinion
        r.append(a[(i-s) % len(a)])
    return r

In my opinion, I would have produced a new list from list slicing as that is more pythonic and more readable.

def shift_mine(a, s):
    # if shifting more than the length of the list, just reduce it to the remainder
    s = s % len(a)
    # concatenate the s-from-the-end items with the beginning-to-the-s-item
    return a[s*-1:]+a[:s*-1]

Thank you so much, Endyd! I can follow your implementation way better than the model solution. — Luk, Jan 08 '19 at 21:01

Python implementation of a cyclic vector rotation

2 Answers2