How to move array elements in python

A collections.deque is optimized for pulling and pushing on both ends. They even have a dedicated rotate() method.

from collections import deque
items = deque([1, 2])
items.append(3)        # deque == [1, 2, 3]
items.rotate(1)        # The deque is now: [3, 1, 2]
items.rotate(-1)       # Returns deque to original state: [1, 2, 3]
item = items.popleft() # deque == [2, 3]

codeforester

35.7k16 gold badges101 silver badges126 bronze badges

answered Jan 27, 2010 at 20:46

4

What about just using pop(0)?

list.pop([i])

Remove the item at the given position in the list, and return it. If no index is specified, a.pop() removes and returns the last item in the list. (The square brackets around the i in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)

tobias_k

79.5k11 gold badges114 silver badges171 bronze badges

answered Dec 5, 2011 at 20:20

JamgoldJamgold

1,7061 gold badge14 silver badges18 bronze badges

7

Numpy can do this using the roll command:

>>> import numpy
>>> a=numpy.arange(1,10) #Generate some data
>>> numpy.roll(a,1)
array([9, 1, 2, 3, 4, 5, 6, 7, 8])
>>> numpy.roll(a,-1)
array([2, 3, 4, 5, 6, 7, 8, 9, 1])
>>> numpy.roll(a,5)
array([5, 6, 7, 8, 9, 1, 2, 3, 4])
>>> numpy.roll(a,9)
array([1, 2, 3, 4, 5, 6, 7, 8, 9])

answered Oct 13, 2012 at 10:57

RichardRichard

51.7k30 gold badges168 silver badges243 bronze badges

3

It depends on what you want to have happen when you do this:

>>> shift([1,2,3], 14)

You might want to change your:

def shift(seq, n):
    return seq[n:]+seq[:n]

to:

def shift(seq, n):
    n = n % len(seq)
    return seq[n:] + seq[:n]

answered Jan 27, 2010 at 21:48

jcdyerjcdyer

18.2k5 gold badges41 silver badges48 bronze badges

4

Simplest way I can think of:

a.append(a.pop(0))

runDOSrun

9,6655 gold badges43 silver badges54 bronze badges

answered Jul 8, 2014 at 12:15

ThijsThijs

3053 silver badges2 bronze badges

2

Just some notes on timing:

If you're starting with a list, l.append(l.pop(0)) is the fastest method you can use. This can be shown with time complexity alone:

• deque.rotate is O(k) (k=number of elements)
• list to deque conversion is O(n)
• list.append and list.pop are both O(1)

So if you are starting with deque objects, you can deque.rotate() at the cost of O(k). But, if the starting point is a list, the time complexity of using deque.rotate() is O(n). l.append(l.pop(0) is faster at O(1).

Just for the sake of illustration, here are some sample timings on 1M iterations:

Methods which require type conversion:

• deque.rotate with deque object: 0.12380790710449219 seconds (fastest)
• deque.rotate with type conversion: 6.853878974914551 seconds
• np.roll with nparray: 6.0491721630096436 seconds
• np.roll with type conversion: 27.558452129364014 seconds

List methods mentioned here:

• l.append(l.pop(0)): 0.32483696937561035 seconds (fastest)
• "shiftInPlace": 4.819645881652832 seconds
• ...

Timing code used is below.

collections.deque

Showing that creating deques from lists is O(n):

from collections import deque
import big_o

def create_deque_from_list(l):
     return deque(l)

best, others = big_o.big_o(create_deque_from_list, lambda n: big_o.datagen.integers(n, -100, 100))
print best

# --> Linear: time = -2.6E-05 + 1.8E-08*n

If you need to create deque objects:

1M iterations @ 6.853878974914551 seconds

setup_deque_rotate_with_create_deque = """
from collections import deque
import random
l = [random.random() for i in range(1000)]
"""

test_deque_rotate_with_create_deque = """
dl = deque(l)
dl.rotate(-1)
"""
timeit.timeit(test_deque_rotate_with_create_deque, setup_deque_rotate_with_create_deque)

If you already have deque objects:

1M iterations @ 0.12380790710449219 seconds

setup_deque_rotate_alone = """
from collections import deque
import random
l = [random.random() for i in range(1000)]
dl = deque(l)
"""

test_deque_rotate_alone= """
dl.rotate(-1)
"""
timeit.timeit(test_deque_rotate_alone, setup_deque_rotate_alone)

np.roll

If you need to create nparrays

1M iterations @ 27.558452129364014 seconds

setup_np_roll_with_create_npa = """
import numpy as np
import random
l = [random.random() for i in range(1000)]
"""

test_np_roll_with_create_npa = """
np.roll(l,-1) # implicit conversion of l to np.nparray
"""

If you already have nparrays:

1M iterations @ 6.0491721630096436 seconds

setup_np_roll_alone = """
import numpy as np
import random
l = [random.random() for i in range(1000)]
npa = np.array(l)
"""

test_roll_alone = """
np.roll(npa,-1)
"""
timeit.timeit(test_roll_alone, setup_np_roll_alone)

"Shift in place"

Requires no type conversion

1M iterations @ 4.819645881652832 seconds

setup_shift_in_place="""
import random
l = [random.random() for i in range(1000)]
def shiftInPlace(l, n):
    n = n % len(l)
    head = l[:n]
    l[:n] = []
    l.extend(head)
    return l
"""

test_shift_in_place="""
shiftInPlace(l,-1)
"""

timeit.timeit(test_shift_in_place, setup_shift_in_place)

l.append(l.pop(0))

Requires no type conversion

1M iterations @ 0.32483696937561035

setup_append_pop="""
import random
l = [random.random() for i in range(1000)]
"""

test_append_pop="""
l.append(l.pop(0))
"""
timeit.timeit(test_append_pop, setup_append_pop)

answered Jul 4, 2017 at 9:12

PurrellPurrell

12k16 gold badges55 silver badges70 bronze badges

4

I also got interested in this and compared some of the suggested solutions with perfplot (a small project of mine).

It turns out that Kelly Bundy's suggestion

tmp = data[shift:]
tmp += data[:shift]

performs very well for all shifts.

Essentially, perfplot performs the shift for increasing large arrays and measures the time. Here are the results:

shift = 1:

shift = 100:

Code to reproduce the plot:

import numpy
import perfplot
import collections


shift = 100


def list_append(data):
    return data[shift:] + data[:shift]


def list_append2(data):
    tmp = data[shift:]
    tmp += data[:shift]
    return tmp


def shift_concatenate(data):
    return numpy.concatenate([data[shift:], data[:shift]])


def roll(data):
    return numpy.roll(data, -shift)


def collections_deque(data):
    items = collections.deque(data)
    items.rotate(-shift)
    return items


def pop_append(data):
    data = data.copy()
    for _ in range(shift):
        data.append(data.pop(0))
    return data


b = perfplot.bench(
    setup=lambda n: numpy.random.rand(n).tolist(),
    kernels=[
        list_append,
        list_append2,
        roll,
        shift_concatenate,
        collections_deque,
        pop_append,
    ],
    n_range=[2 ** k for k in range(7, 20)],
    xlabel="len(data)",
)
b.show()
b.save("shift100.png")

answered Jul 20, 2018 at 15:04

Nico SchlömerNico Schlömer

48.7k24 gold badges186 silver badges223 bronze badges

6

If you just want to iterate over these sets of elements rather than construct a separate data structure, consider using iterators to construct a generator expression:

def shift(l,n):
    return itertools.islice(itertools.cycle(l),n,n+len(l))

>>> list(shift([1,2,3],1))
[2, 3, 1]

answered Oct 29, 2012 at 15:34

Phil HPhil H

19.4k7 gold badges64 silver badges103 bronze badges

This also depends on if you want to shift the list in place (mutating it), or if you want the function to return a new list. Because, according to my tests, something like this is at least twenty times faster than your implementation that adds two lists:

def shiftInPlace(l, n):
    n = n % len(l)
    head = l[:n]
    l[:n] = []
    l.extend(head)
    return l

In fact, even adding a l = l[:] to the top of that to operate on a copy of the list passed in is still twice as fast.

Various implementations with some timing at http://gist.github.com/288272

answered Jan 27, 2010 at 23:10

keturnketurn

4,7503 gold badges28 silver badges40 bronze badges

3

For an immutable implementation, you could use something like this:

def shift(seq, n):
    shifted_seq = []
    for i in range(len(seq)):
        shifted_seq.append(seq[(i-n) % len(seq)])
    return shifted_seq

print shift([1, 2, 3, 4], 1)

dabuno

3433 silver badges4 bronze badges

answered Feb 25, 2012 at 21:49

BittercoderBittercoder

11.4k9 gold badges57 silver badges76 bronze badges

Possibly a ringbuffer is more suitable. It is not a list, although it is likely that it can behave enough like a list for your purposes.

The problem is that the efficiency of a shift on a list is O(n), which becomes significant for large enough lists.

Shifting in a ringbuffer is simply updating the head location which is O(1)

answered Jan 27, 2010 at 21:59

John La RooyJohn La Rooy

286k51 gold badges358 silver badges498 bronze badges

If efficiency is your goal, (cycles? memory?) you may be better off looking at the array module: http://docs.python.org/library/array.html

Arrays do not have the overhead of lists.

As far as pure lists go though, what you have is about as good as you can hope to do.

answered Jan 27, 2010 at 20:47

recursiverecursive

81.9k32 gold badges147 silver badges236 bronze badges

0

I think you are looking for this:

a.insert(0, x)

answered Mar 25, 2014 at 9:46

1

Another alternative:

def move(arr, n):
    return [arr[(idx-n) % len(arr)] for idx,_ in enumerate(arr)]

answered Apr 9, 2016 at 17:05

damiodamio

5,8513 gold badges35 silver badges55 bronze badges

def solution(A, K):
    if len(A) == 0:
        return A

    K = K % len(A)

    return A[-K:] + A[:-K]

# use case
A = [1, 2, 3, 4, 5, 6]
K = 3
print(solution(A, K))

For example, given

A = [3, 8, 9, 7, 6]
K = 3

the function should return [9, 7, 6, 3, 8]. Three rotations were made:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

For another example, given

A = [0, 0, 0]
K = 1

the function should return [0, 0, 0]

Given

A = [1, 2, 3, 4]
K = 4

the function should return [1, 2, 3, 4]

RobC

20.8k20 gold badges66 silver badges74 bronze badges

answered Nov 15, 2019 at 8:41

I take this cost model as a reference:

http://scripts.mit.edu/~6.006/fall07/wiki/index.php?title=Python_Cost_Model

Your method of slicing the list and concatenating two sub-lists are linear-time operations. I would suggest using pop, which is a constant-time operation, e.g.:

def shift(list, n):
    for i in range(n)
        temp = list.pop()
        list.insert(0, temp)

shanethehat

15.4k11 gold badges55 silver badges85 bronze badges

answered Feb 21, 2012 at 22:32

herrfzherrfz

4,7283 gold badges25 silver badges37 bronze badges

2

I don't know if this is 'efficient', but it also works:

x = [1,2,3,4]
x.insert(0,x.pop())

EDIT: Hello again, I just found a big problem with this solution! Consider the following code:

class MyClass():
    def __init__(self):
        self.classlist = []

    def shift_classlist(self): # right-shift-operation
        self.classlist.insert(0, self.classlist.pop())

if __name__ == '__main__':
    otherlist = [1,2,3]
    x = MyClass()

    # this is where kind of a magic link is created...
    x.classlist = otherlist

    for ii in xrange(2): # just to do it 2 times
        print '\n\n\nbefore shift:'
        print '     x.classlist =', x.classlist
        print '     otherlist =', otherlist
        x.shift_classlist() 
        print 'after shift:'
        print '     x.classlist =', x.classlist
        print '     otherlist =', otherlist, '<-- SHOULD NOT HAVE BIN CHANGED!'

The shift_classlist() method executes the same code as my x.insert(0,x.pop())-solution, otherlist is a list indipendent from the class. After passing the content of otherlist to the MyClass.classlist list, calling the shift_classlist() also changes the otherlist list:

CONSOLE OUTPUT:

before shift:
     x.classlist = [1, 2, 3]
     otherlist = [1, 2, 3]
after shift:
     x.classlist = [3, 1, 2]
     otherlist = [3, 1, 2] <-- SHOULD NOT HAVE BIN CHANGED!



before shift:
     x.classlist = [3, 1, 2]
     otherlist = [3, 1, 2]
after shift:
     x.classlist = [2, 3, 1]
     otherlist = [2, 3, 1] <-- SHOULD NOT HAVE BIN CHANGED!

I use Python 2.7. I don't know if thats a bug, but I think it's more likely that I missunderstood something here.

Does anyone of you know why this happens?

answered May 17, 2013 at 16:57

wese3112wese3112

931 gold badge1 silver badge6 bronze badges

2

The following method is O(n) in place with constant auxiliary memory:

def rotate(arr, shift):
  pivot = shift % len(arr)
  dst = 0
  src = pivot
  while (dst != src):
    arr[dst], arr[src] = arr[src], arr[dst]
    dst += 1
    src += 1
    if src == len(arr):
      src = pivot
    elif dst == pivot:
      pivot = src

Note that in python, this approach is horribly inefficient compared to others as it can't take advantage of native implementations of any of the pieces.

answered Jun 11, 2015 at 12:19

DRayXDRayX

1,0232 gold badges12 silver badges19 bronze badges

2

I have similar thing. For example, to shift by two...

def Shift(*args):
    return args[len(args)-2:]+args[:len(args)-2]

answered Jan 13, 2016 at 18:19

eyoeldefareeyoeldefare

1,9471 gold badge14 silver badges24 bronze badges

I think you've got the most efficient way

def shift(l,n):
    n = n % len(l)  
    return l[-U:] + l[:-U]

answered Aug 23, 2017 at 21:17

john ktejikjohn ktejik

5,6874 gold badges49 silver badges53 bronze badges

Jon Bentley in Programming Pearls (Column 2) describes an elegant and efficient algorithm for rotating an n-element vector x left by i positions:

Let's view the problem as transforming the array ab into the array ba, but let's also assume that we have a function that reverses the elements in a specified portion of the array. Starting with ab, we reverse a to get arb, reverse b to get arbr, and then reverse the whole thing to get (arbr)r, which is exactly ba. This results in the following code for rotation:

reverse(0, i-1)
reverse(i, n-1)
reverse(0, n-1)

This can be translated to Python as follows:

def rotate(x, i):
    i %= len(x)
    x[:i] = reversed(x[:i])
    x[i:] = reversed(x[i:])
    x[:] = reversed(x)
    return x

Demo:

>>> def rotate(x, i):
...     i %= len(x)
...     x[:i] = reversed(x[:i])
...     x[i:] = reversed(x[i:])
...     x[:] = reversed(x)
...     return x
... 
>>> rotate(list('abcdefgh'), 1)
['b', 'c', 'd', 'e', 'f', 'g', 'h', 'a']
>>> rotate(list('abcdefgh'), 3)
['d', 'e', 'f', 'g', 'h', 'a', 'b', 'c']
>>> rotate(list('abcdefgh'), 8)
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
>>> rotate(list('abcdefgh'), 9)
['b', 'c', 'd', 'e', 'f', 'g', 'h', 'a']

answered Jul 1, 2018 at 16:47

Eugene YarmashEugene Yarmash

134k37 gold badges309 silver badges366 bronze badges

I was looking for in place solution to this problem. This solves the purpose in O(k).

def solution(self, list, k):
    r=len(list)-1
    i = 0
    while i

answered Dec 25, 2019 at 16:14

AnkitAnkit

474 bronze badges

What is the use case? Often, we don't actually need a fully shifted array --we just need to access a handful of elements in the shifted array.

Getting Python slices is runtime O(k) where k is the slice, so a sliced rotation is runtime N. The deque rotation command is also O(k). Can we do better?

Consider an array that is extremely large (let's say, so large it would be computationally slow to slice it). An alternative solution would be to leave the original array alone and simply calculate the index of the item that would have existed in our desired index after a shift of some kind.

Accessing a shifted element thus becomes O(1).

def get_shifted_element(original_list, shift_to_left, index_in_shifted):
    # back calculate the original index by reversing the left shift
    idx_original = (index_in_shifted + shift_to_left) % len(original_list)
    return original_list[idx_original]

my_list = [1, 2, 3, 4, 5]

print get_shifted_element(my_list, 1, 2) ----> outputs 4

print get_shifted_element(my_list, -2, 3) -----> outputs 2 

answered Oct 31, 2017 at 23:53

Following function copies sent list to a templist, so that pop function does not affect the original list:

def shift(lst, n, toreverse=False):
    templist = []
    for i in lst: templist.append(i)
    if toreverse:
        for i in range(n):  templist = [templist.pop()]+templist
    else:
        for i in range(n):  templist = templist+[templist.pop(0)]
    return templist

Testing:

lst = [1,2,3,4,5]
print("lst=", lst)
print("shift by 1:", shift(lst,1))
print("lst=", lst)
print("shift by 7:", shift(lst,7))
print("lst=", lst)
print("shift by 1 reverse:", shift(lst,1, True))
print("lst=", lst)
print("shift by 7 reverse:", shift(lst,7, True))
print("lst=", lst)

Output:

lst= [1, 2, 3, 4, 5]
shift by 1: [2, 3, 4, 5, 1]
lst= [1, 2, 3, 4, 5]
shift by 7: [3, 4, 5, 1, 2]
lst= [1, 2, 3, 4, 5]
shift by 1 reverse: [5, 1, 2, 3, 4]
lst= [1, 2, 3, 4, 5]
shift by 7 reverse: [4, 5, 1, 2, 3]
lst= [1, 2, 3, 4, 5]

answered Dec 14, 2017 at 15:21

rnsornso

22.5k22 gold badges102 silver badges213 bronze badges

For a list X = ['a', 'b', 'c', 'd', 'e', 'f'] and a desired shift value of shift less than list length, we can define the function list_shift() as below

def list_shift(my_list, shift):
    assert shift < len(my_list)
    return my_list[shift:] + my_list[:shift]

Examples,

list_shift(X,1) returns ['b', 'c', 'd', 'e', 'f', 'a'] list_shift(X,3) returns ['d', 'e', 'f', 'a', 'b', 'c']

answered Aug 2, 2018 at 4:48

helcodehelcode

1,7101 gold badge11 silver badges29 bronze badges

2

I'm "old school" I define efficiency in lowest latency, processor time and memory usage, our nemesis are the bloated libraries. So there is exactly one right way:

    def rotatel(nums):
        back = nums.pop(0)
        nums.append(back)
        return nums

answered Dec 26, 2020 at 0:35

Below is an efficient algorithm that doesn't require the use of any additional data structure:

def rotate(nums: List[int], k: int):

    k = k%len(nums)
    l, r = 0, len(nums)-1
    while (l

answered Jan 3 at 14:01

How do you move values in an array?

In this article, we will go through the ways to shift an element of an array in Java..

Use the for Loop and a temp Variable to Shift an Array in Java..

Use the skip() Method to Shift an Array in Java 8..

Use the Collections. rotate(List list, int distance) to Shift an Array in Java..

Related Article - Java Array..

How do you move items in a list in Python?

In Python, the easiest way to shift values in a list is with the Python list pop(), insert(), and append() functions. You can also use the deque() data structure from the Python collections module to shift a list. You can also use list slicing to shift a list forward or backwards in Python.

How do I move an array to another array in Python?

ALGORITHM: STEP 1: Declare and initialize an array. STEP 2: Declare another array of the same size as of the first one. STEP 3: Loop through the first array from 0 to length of the array and copy an element from the first array to the second array that is arr1[i] = arr2[i].

How do you move an element in an array in Numpy?

If we want to right-shift or left-shift the elements of a NumPy array, we can use the numpy. roll() method in Python. The numpy. roll() method is used to roll array elements along a specified axis.