0

I'm looking for an elegant way to write a simple function that would shift the elements of list by a given number of positions, while keeping the list of the same length and padding empty positions with a default value. This would be the docstring of the function:

def shift_list(l, shift, empty=0):
    """
    Shifts the elements of a list **l** of **shift** positions,
    padding new items with **empty**::

        >>> l = [0, 1, 4, 5, 7, 0]
        >>> shift_list(l, 3)
        [0, 0, 0, 0, 1, 4]
        >>> shift_list(l, -3)
        [5, 7, 0, 0, 0, 0]
        >>> shift_list(l, -8)
        [0, 0, 0, 0, 0, 0]
    """
    pass

How would you proceed ? Any help greatly appreciated !

xApple
  • 6,150
  • 9
  • 48
  • 49

7 Answers7

3

I'd use slice assignment:

def shift_list(l, shift, empty=0):
    src_index = max(-shift, 0)
    dst_index = max(shift, 0)
    length = max(len(l) - abs(shift), 0)
    new_l = [empty] * len(l)
    new_l[dst_index:dst_index + length] = l[src_index:src_index + length]
    return new_l
Sven Marnach
  • 574,206
  • 118
  • 941
  • 841
2

If you can use a deque instead of a list, it has a few nice features that make it a natural choice for this problem. Working from the left of a deque is much less expensive than doing so on a list. Also it has a maxlen argument that can be used to make the code prettier and faster. I'm rather sure using itertools.repeat instead of [empty] * n is more efficient, both memory-wize and with regards to speed.

from collections import deque
from itertools import repeat

def shift_list(l, n, empty=0):
    d = deque(l, maxlen=len(l))
    if n > 0:
        d.extendleft(repeat(empty, min(n, len(l))))
    elif n < 0:
        d.extend(repeat(empty, min(-n, len(l))))
    # return list(d) to pass your doctest, at the cost of performance
    return d

A bit of a warning though -- while the time complexity of iterating over the elements of a deque is comparable to doing the same on a list, item lookup may be rather expensive -- it depends on the index: s[0] and s[-1] is very fast, s[len(s)/2] is the most expensive. So if you do a lot of lookups, consider either using another solution, or converting the result back to a list. See this page for an overview.

Lauritz V. Thaulow
  • 49,139
  • 12
  • 73
  • 92
1

A bit naïve, but job's done.

def shift(l, shift, empty=0):
    reverse = False
    if shift < 0:
        reverse = True
        shift = abs(shift)
    while (shift > 0) :
        if reverse:
            l.pop(0)
            l.append(empty)
        else:
            l.pop()
            l.insert(0, empty)
        shift-=1



l = [0, 1, 4, 5, 7, 0]
shift(l, 3)
print l
l = [0, 1, 4, 5, 7, 0]
shift(l, -3)
print l
l = [0, 1, 4, 5, 7, 0]
shift(l, -8)
print l
oyo
  • 1,906
  • 2
  • 16
  • 22
  • It works, but the doctest given wouldn't pass since the list is modified in place. – xApple Feb 09 '12 at 13:33
  • This solution suffers from the same performance problems as Aram's solution, it has [O(len(l)*shift)](http://en.wikipedia.org/wiki/Big_O_notation) time complexity. Both `l.pop(0)` and `l.insert(0, empty)` are [very expensive operations](http://wiki.python.org/moin/TimeComplexity). – Lauritz V. Thaulow Feb 09 '12 at 13:35
1

A non intuitive way of rotating a list

def shift_list(l, shift, empty=0):
    l1=[empty]*len(l)+l+[empty]*len(l)
    l1=l1[len(l)-shift:][0:len(l)]
    return l1+[empty]*(len(l)-len(l1))
Abhijit
  • 62,056
  • 18
  • 131
  • 204
0

The following method does not answer the question, but I still find it helpful for those who would like to shift the valuse like a circle.

# Shift to the left.
shift = 1
a = [1, 2, 3, 4]
a = a[shift:] + a[:shift]
# [2, 3, 4, 1]

or

# Shift to the right.
shift = -1
a = [1, 2, 3, 4]
a = a[shift:] + a[:shift]
# [4, 1, 2, 3]
fflores
  • 192
  • 1
  • 6
  • Why do you think that it doesn't answer the question? – mkrieger1 Apr 09 '23 at 21:28
  • @mkrieger1 The author of the question wanted a little bit different behavior, he wanted to fill the the left or right side with zeros, it's like shifting bits in C/C++. While my shift works like a linked list that is linked like a circle where the end node is connected to the start node. – fflores Apr 09 '23 at 21:51
  • Then you should have posted it as an answer to this question instead: https://stackoverflow.com/questions/2150108/efficient-way-to-rotate-a-list-in-python – mkrieger1 Apr 09 '23 at 22:04
  • @mkrieger1 Yes, you are right, It would be better if I posted it there, I just didn't find the right question instantly, but thanks to your link, now it would be easier for any to find the other solutions. They are related any way. – fflores Apr 09 '23 at 22:09
0

Would this do it?

def shift_list(l, shift, empty=0):
    while shift > 0:
        l.insert(0,empty)
        l.pop()
        shift -= 1
    ​return l
Sven Marnach
  • 574,206
  • 118
  • 941
  • 841
Aram Kocharyan
  • 20,165
  • 11
  • 81
  • 96
  • It would, but it is `O(len(l)*shift)`, which is rather suboptimal. (And also get rid of those braces, semicolons and redundant parens. `shift--` isn't Python either.) – Sven Marnach Feb 09 '12 at 11:32
0

I would do it like this:

def shift_list(l, shift, empty=0):
    if shift > 0:
        return [empty] * shift + l[:-shift]

    return l[-shift:] + [empty] * abs(shift)
Wheerd
  • 1