Tuesday, February 4, 2020

Circular shift of lists in python

Scenario

Assume I have a list in python
a = [ -2, -1, 0, 1, 2 ]
(an admittedly simple list here with integer numbers).
I want to shift these entries in the list to the left or right so that the entries moving out of the list enter the list again at the other end e.g. I want to shift 2 to the left to get this list:
[0, 1, 2, -2, -1]

Solutions

There are solutions using numpy but I want to present another easy solution just using slices.
shift = 2
x = a[shift:]       # This is [ 0, 1, 2 ]
y = a[:shift]       # This is [ -2, -1 ]
print( x + y )

[0, 1, 2, -2, -1]
I am
  • setting my shift value to 2
  • creating a slice from index 2 to the end of the list
  • creating a slice from the beginning of the list until index - 1
  • adding the two slices to get the shifted result

    This also works for negative shift values (shift to the right) which is a particularily nice feature of the pythong [:] operator.

    shift = -1
    x = a[shift:]       # This is [ 2 ]
    y = a[:shift]       # This is [ -2, -1, 0, 1 ]
    print( x + y ) 
    
    [2, -2, -1, 0, 1]
    

    Add-on: calculate the new index of a shifted element

    Starting with
    a = [ -2, -1, 0, 1, 2 ]
    
    the element -2 has index 0. The shift 2 to the left result
    [0, 1, 2, -2, -1]
    
    puts element -2 at index 3.

    How can I calculate that?

    
    def index_after_shift( old_index, shift ):
      return ( old_index - shift ) % len(a) 
    
    # Examples
    for shift in [2, -1 , 6 ]:
      for ind in [ 0,1,2,3,4]:
        print( ind, shift, index_after_shift( ind, shift ) )
      print()
    
    0 2 3
    1 2 4
    2 2 0
    3 2 1
    4 2 2
    
    0 -1 1
    1 -1 2
    2 -1 3
    3 -1 4
    4 -1 0
    
    0 6 4
    1 6 0
    2 6 1
    3 6 2
    4 6 3
    
    The function index_after_shift calculates the new index.
    A shift 2 to the left i.e. shift = 2 means that we subtract 2 from the current index to get to the new one therefore old_index - shift. This is easily understandable for indexes 2, 3, 4, ... which will become 0, 1, 2, ....
    What do we do with smaller indexes?>
    Here we are using the modulo function which will do the necessary calculation for us e.g.
    shift = 2
    old_index = 1
    # length of a is 5
    ( old_index - shift ) % len(a)
    # = ( 1 - 2 ) % 5
    # = -1 % 5
    # = 4
    
    The modulo has converted the negative number resulting from the subtraction into a positive one.

    shift to the right means we have to add something to the index to get to our new index (since the variable shift is negative for right shifts we subtract a negative number in the function which results in the addition of a positive number).