在python中旋转列表的有效方法

问题:在python中旋转列表的有效方法

在python中旋转列表的最有效方法是什么?现在我有这样的事情:

>>> def rotate(l, n):
...     return l[n:] + l[:n]
... 
>>> l = [1,2,3,4]
>>> rotate(l,1)
[2, 3, 4, 1]
>>> rotate(l,2)
[3, 4, 1, 2]
>>> rotate(l,0)
[1, 2, 3, 4]
>>> rotate(l,-1)
[4, 1, 2, 3]

有没有更好的办法?

What is the most efficient way to rotate a list in python? Right now I have something like this:

>>> def rotate(l, n):
...     return l[n:] + l[:n]
... 
>>> l = [1,2,3,4]
>>> rotate(l,1)
[2, 3, 4, 1]
>>> rotate(l,2)
[3, 4, 1, 2]
>>> rotate(l,0)
[1, 2, 3, 4]
>>> rotate(l,-1)
[4, 1, 2, 3]

Is there a better way?


回答 0

A collections.deque已针对两端的推拉进行了优化。他们甚至有专门的rotate()方法。

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]

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]

回答 1

只是使用pop(0)呢?

list.pop([i])

删除列表中给定位置的项目,然后将其返回。如果未指定索引,则a.pop()删除并返回列表中的最后一项。(i方法签名中的方括号表示该参数是可选的,而不是您应该在该位置键入方括号。您会在Python库参考中经常看到此表示法。)

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.)


回答 2

Numpy可以使用以下roll命令执行此操作:

>>> 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])

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])

回答 3

这取决于执行此操作时想要发生的事情:

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

您可能要更改:

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

至:

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

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]

回答 4

我想到的最简单的方法:

a.append(a.pop(0))

Simplest way I can think of:

a.append(a.pop(0))

回答 5

如果只想遍历这些元素集而不是构造单独的数据结构,请考虑使用迭代器构造生成器表达式:

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

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

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]

回答 6

这还取决于您是否希望将列表移到适当位置(对其进行突变),或者是否要让函数返回新列表。因为根据我的测试,类似这样的事情至少比添加两个列表的实现快二十倍:

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

实际上,即使添加 l = l[:]在其顶部来对传入列表的副本进行操作,其速度仍然是其两倍。

http://gist.github.com/288272上有一定时间的各种实现

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


回答 7

关于时间的一些注意事项:

如果您从列表开始,那l.append(l.pop(0))是可以使用的最快方法。仅用时间复杂度就可以显示出来:

  • deque.rotate为O(k)(k =元素数)
  • 要进行双端队列转换的列表是O(n)
  • list.append和list.pop都是O(1)

因此,如果您从deque对象开始,则可以deque.rotate()以O(k)为代价。但是,如果起点是列表,则使用的时间复杂度deque.rotate()为O(n)。l.append(l.pop(0)在O(1)更快。

只是为了说明,这是一些1M迭代的示例时序:

需要类型转换的方法:

  • deque.rotate使用双端队列对象:0.12380790710449219秒(最快)
  • deque.rotate类型转换:6.885387997415551秒
  • np.roll使用nparray:6.0491721630096436秒
  • np.roll类型转换:27.558452129364014秒

列出这里提到的方法:

  • l.append(l.pop(0))0.32483696937561035秒(最快)
  • shiftInPlace”: 4.819645881652832秒

使用的时序代码如下。


collections.deque

显示从列表创建双端队列是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

如果需要创建双端队列对象:

1M次迭代@ 6.853878974914551秒

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)

如果您已经有双端队列对象:

1M次迭代@ 0.12380790710449219秒

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

如果您需要创建nparrays

1M次迭代@ 27.558452129364014秒

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
"""

如果您已经有nparrays:

1M次迭代@ 6.0491721630096436秒

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)

“原地转移”

不需要类型转换

1M次迭代@ 4.819645881652832秒

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))

不需要类型转换

1M次迭代@ 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)

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)

回答 8

我对此也很感兴趣,并将一些建议的解决方案与perfplot(我的一个小项目)进行了比较。

原来是

for _ in range(n):
    data.append(data.pop(0))

迄今为止小班最快的方法n

对于较大的n

data[n:] + data[:n]

还不错

本质上,perfplot执行移位以增加大型阵列并测量时间。结果如下:

shift = 1

shift = 100


复制剧情的代码:

import numpy
import perfplot
import collections


shift = 100


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


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):
    for _ in range(shift):
        data.append(data.pop(0))
    return data


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

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

It turns out that

for _ in range(n):
    data.append(data.pop(0))

is by far the fastest method for small shifts n.

For larger n,

data[n:] + data[:n]

isn’t bad.

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 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):
    for _ in range(shift):
        data.append(data.pop(0))
    return data


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

回答 9

可能更适合使用环形缓冲区。它不是列表,尽管出于您的目的,它的行为可能像列表一样足够。

问题在于列表上的移位效率为O(n),这对于足够大的列表而言变得非常重要。

移入环形缓冲区仅是更新头部位置,即O(1)

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)


回答 10

对于不可变的实现,您可以使用如下所示的内容:

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)

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)

回答 11

如果效率是您的目标(循环?内存?),那么最好查看一下数组模块:http : //docs.python.org/library/array.html

数组没有列表的开销。

就纯粹的清单而言,您所拥有的和您希望的一样好。

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.


回答 12

我认为您正在寻找:

a.insert(0, x)

I think you are looking for this:

a.insert(0, x)

回答 13

另一种选择:

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

Another alternative:

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

回答 14

我将此成本模型作为参考:

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

切片列表并连接两个子列表的方法是线性时间操作。我建议使用pop,这是一个恒定时间的操作,例如:

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

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)

回答 15

我不知道这是否“有效”,但它也有效:

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

编辑:您好,我刚刚发现此解决方案有大问题!考虑以下代码:

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!'

shift_classlist()方法执行与我的x.insert(0,x.pop())-solution相同的代码,otherlist是与该类无关的列表。将otherlist的内容传递到MyClass.classlist列表后,调用shift_classlist()也会更改otherlist列表:

控制台输出:

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!

我使用Python 2.7。我不知道这是否是一个错误,但我认为我很可能在这里误解了一些东西。

你们当中有人知道为什么会这样吗?

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?


回答 16

下面的方法是在常量内存为常数的情况下使用O(n):

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

请注意,在python中,这种方法与其他方法相比效率非常低,因为它无法利用任何部分的本机实现。

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.


回答 17

我有类似的事情。例如,要移动两个…

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

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

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

回答 18

我认为您有最有效的方法

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

I think you’ve got the most efficient way

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

回答 19

用例是什么?通常,我们实际上并不需要一个完全移位的数组-我们只需要访问移位数组中的少数元素即可。

获取Python切片是运行时O(k),其中k是切片,因此切片旋转是运行时N。双端队列旋转命令也是O(k)。我们可以做得更好吗?

考虑一个非常大的数组(比方说,太大,将其切成切片在计算上会很慢)。另一种解决方案是不保留原始数组,仅计算某种移位后在所需索引中已经存在的项目的索引。

因此,访问已移位的元素将变为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 

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 

回答 20

以下函数将发送的列表复制到临时列表,以便pop函数不会影响原始列表:

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

测试:

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)

输出:

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]

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]

回答 21

乔恩·本特利(Jon Bentley)在“ 编程珍珠”(第2列)中描述了一种优雅而有效的算法,用于旋转位置左侧的n元素矢量:xi

让我们将问题视为将数组ab转换为array ba,但还要假设我们有一个函数可以反转数组指定部分中的元素。首先ab,我们反转a以获得,反转获得 ,然后反转整个事物以得到,正是这样。这将导致以下代码旋转:arbbarbr(arbr)rba

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

可以将其转换为Python,如下所示:

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

演示:

>>> 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']

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']

回答 22

为列表X = ['a', 'b', 'c', 'd', 'e', 'f']和期望的位移值shift 小于列表长度,我们可以定义函数list_shift(),如下

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

例子,

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

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']


回答 23

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))

例如,给定

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

该函数应该返回[9, 7, 6, 3, 8]。进行了三个轮换:

[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]

再举一个例子

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

该函数应返回 [0, 0, 0]

给定

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

该函数应返回 [1, 2, 3, 4]

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]


回答 24

我一直在寻找解决此问题的方法。这解决了O(k)中的目的。

def solution(self, list, k):
    r=len(list)-1
    i = 0
    while i<k:
        temp = list[0]
        list[0:r] = list[1:r+1]
        list[r] = temp
        i+=1
    return list

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<k:
        temp = list[0]
        list[0:r] = list[1:r+1]
        list[r] = temp
        i+=1
    return list

回答 25

具有与其他语言中的shift类似的功能:

def shift(l):
    x = l[0]
    del(l[0])
    return x

for similar functionality as shift in other languages:

def shift(l):
    x = l[0]
    del(l[0])
    return x