Shift elements left by n indices in a list

Question

For the following question, the function

• should mutate the original list

• should NOT create any new lists

• should NOT return anything

Functions that do not create new lists are said to be ”in place.” Such functions are often desirable because they do not require extra memory to operate.

Define shift_left, a function that takes a list and shifts each element in the list to the left by n indices. If elements start ”falling off” on the left, they are placed back on the right. NOTE: you may assume that n is a non-negative integer.

def shift_left(lst, n):
"""Shifts the elements of lst over by n indices.
>>> lst = [1, 2, 3, 4, 5]
>>> shift_left(lst, 2)
>>> lst
[3, 4, 5, 1, 2]
"""

Below is the solution:

def shift_left(lst, n):
    """Shifts the lst over by n indices

    >>> lst = [1, 2, 3, 4, 5]
    >>> shift_left(lst, 2)
    >>> lst
    [3, 4, 5, 1, 2]
    """
    assert (n > 0), "n should be non-negative integer"
    def shift(ntimes):
        if ntimes == 0:
            return
        else:
            temp = lst[0]
            for index in range(len(lst) - 1):
                lst[index] = lst[index + 1]         
            lst[index + 1] = temp
            return shift(ntimes-1)
    return shift(n)

I have yet to learn about raising exceptions in Python.

Can this code be more elegant by following a recursive approach? As of now, space (stack frame) usage can be considered secondary.

Answer 1

Some suggestions:

• The assignment says “ you may assume that n is a non-negative integer”, but the condition you check is “n > 0”. Since n = 0 is non-negative (and corresponds to no mutation of the list), you should handle that as well.

• An assert should only really be used to check that the program isn’t in an impossible situation. It would be preferable to use exceptions, and it’s very simple to do so:

  if n < 0:
      raise ValueError("Input %d is not a non-negative integer" % n)
  

  (Alternatively, you could implement negative indices as right-shifting, but I’ll leave that for now.)

• You can condense the for loop in shift with a list slice: the following code achieves the same effect:

  lst[:-1] = lst[1:]
  

  Everything except the last element in lst is assigned to the element one to its left in the original list.

  You can extend this list slicing to do away with the temp variable (which is probably a bit more memory efficient), and do the list slicing in a single line. Shifting one position to the left is achieved with the line

  lst[:] = lst[1:] + [lst[0]]
  

• At that point, the shift() function is almost so simple that you can do away with it entirely, and recurse only on the shift_left() function. Here’s what I reduced it to:

  if n == 0:
      return
  else:
      lst[:] = lst[1:] + [lst[0]]
      shift_left(lst, n-1)
  

Answer 2

Can we make this code more elegant by following recursive approach?

Definitely - it is relatively simple to recast this problem in a recursive fashion. Note that shifting left by two places is the same as shifting left by one place twice, so:

def shift_left(lst, n):
    """Shifts the lst over by n indices

    >>> lst = [1, 2, 3, 4, 5]
    >>> shift_left(lst, 2)
    >>> lst
    [3, 4, 5, 1, 2]
    """
    if n < 0:
        raise ValueError('n must be a positive integer')
    if n > 0:
        lst.insert(0, lst.pop(-1))  # shift one place
        shift_left(lst, n-1)  # repeat

Note that this splits the problem into three cases:

• Negative n: error state, raise an exception (I generally wouldn't use an assert for this - see e.g. Best practice for Python Assert);
• Positive n: recursive case, shift and repeat; and
• Zero n: nothing left to do!

However, note that the problem states that "you may assume that n is a non-negative integer" - I would take this to mean that you don't need to explicitly handle the n < 0 cases.

One downside of this particular approach is that it fails if lst == [] and n > 0, as there's nothing to shift. You will have to decide what should happen in that case and handle it appropriately.

Answer 3

Naming

The variable name has to be as descriptive as possible. Don´t use generic names.

temp may be anything, I only know that is lasts for little time, (that I already know because variables declared inside functions remain inside functions)

temp = lst[0]

Never name your variable temp, I suggest first

Modularize the code

def shift_left_once(lst):
    temp = lst[0]
    for index in range(len(lst) - 1):
        lst[index] = lst[index + 1]         
    lst[index + 1] = temp

def shift_left(lst, n):
    """Shifts the lst over by n indices

    >>> lst = [1, 2, 3, 4, 5]
    >>> shift_left(lst, 2)
    >>> lst
    [3, 4, 5, 1, 2]
    """
    assert (n >= 0), "n should be non-negative integer"
    for _ in range(n):
        shift_left_once(lst)

I wrote a simpler function that only shifts one time, the other function just calls it many times.

---

If you are forced to use recursion (that should be used very rarely in Python not only because it is slow but also because it is weird (programmers are much more used to explicit loops)) you can:

def shift_left(lst, n):
    """Shifts the lst over by n indices

    >>> lst = [1, 2, 3, 4, 5]
    >>> shift_left(lst, 2)
    >>> lst
    [3, 4, 5, 1, 2]
    """
    assert (n >= 0), "n should be non-negative integer"
    if n == 0:
        return
    shift_left_once(lst)
    shift_left(lst, n-1)

Answer 4

• More on naming. It is not your fault; just keep in mind that for a computer scientist shift has a very precise meaning. Once we start placing falling-off elements back at the right, the algorithm becomes rotate.

• Performance. Your approach has an \$O({l}\times{n})\$ complexity. There are two ways to drive the complexity down to just \$O(l)\$.

  • Observe that the element at index i ends up at index (i + ntimes) % len(lst), in other words index i is a final place for an element at (i + ntimes) % len(lst). It means that the loop

    tmp = lst[i]
    dst = i
    src = (dst - ntimes) % len
    while src != i:
       lst[dst] = lst[src]
       dst = src
       src = (dst - ntimes) % len
    lst[dst] = tmp
    

    does rotate a certain subset (aka orbit) of the list, and running it against all orbits achieves rotation in \$O(len)\$ operations with an asymptotic constant close to 1. Figuring out how these orbits are organized requires a certain grasp of (elementary) number theory; I highly recommend to study it.

  • More practical approach (still \$O(len)\$ with a slightly worse asymptotics) involves 3 reversals.

    Let's say we need to rotate the list a b c d e by two positions into c d e a b.

    • Reverse the first two elements giving b a c d e
    • Reverse the remaining portion of the list giving b a e d c
    • Now reversing the whole list gives a desired result: c d e a b

Answer 5

I use the same idea that you had: pop elements on the left and append them on the right. However, instead of recursion, I took all the elements I needed to pop at once, by taking n % len(l) (because the result of shifting a list of 5 elements 7 times is the same as the result of shifting it 2 times). This approach is simpler and uses less space than your recursive approach.

To mutate the original list, I used the extend method, which is useful if you wanted to extend list with elements from another list instead of appending them one by one.

def shift_left(l, n):
    """ 
    In place shift n elements of list l to the left. 
    Won't work on strings.
    """  
    n = n % len(l)
    head = l[:n]
    l[:n] = []
    l.extend(head)
    return l

Some unit tests, for sanity's sake:

import unittest
from random import randrange

class TestShiftLeft(unittest.TestCase):
    def test_zero_shifts(self):
        self.assertEqual([1], shift_left([1], 0))
        self.assertEqual([1, 2], shift_left([1, 2], 0))

    def test_single_element(self):
        self.assertEqual([1], shift_left([1], 1))
        self.assertEqual([1], shift_left([1], 2))
        self.assertEqual([1], shift_left([1], 3))

    def test_two_elements(self):
        self.assertEqual([2, 1], shift_left([1, 2], 1))
        self.assertEqual([1, 2], shift_left([1, 2], 2))
        self.assertEqual([2, 1], shift_left([1, 2], 3))
        self.assertEqual([1, 2], shift_left([1, 2], 4))

    def test_odd_number_elements(self):
        self.assertEqual([2, 3, 1], shift_left([1, 2, 3], 1))
        self.assertEqual([3, 1, 2], shift_left([1, 2, 3], 2))
        self.assertEqual([1, 2, 3], shift_left([1, 2, 3], 3))
        self.assertEqual([2, 3, 1], shift_left([1, 2, 3], 4))

    def test_even_number_elements(self):
        self.assertEqual([2, 3, 4, 1], shift_left([1, 2, 3, 4], 1))
        self.assertEqual([3, 4, 1, 2], shift_left([1, 2, 3, 4], 2))
        self.assertEqual([4, 1, 2, 3], shift_left([1, 2, 3, 4], 3))
        self.assertEqual([1, 2, 3, 4], shift_left([1, 2, 3, 4], 4))
        self.assertEqual([2, 3, 4, 1], shift_left([1, 2, 3, 4], 5))

    def test_len_l_shift(self):
        l = list(range(randrange(1000)))
        self.assertEqual(l, shift_left(l, len(l)))

if __name__ == '__main__':
    unittest.main()