python - 在 Python 中生成循环移位/减少拉丁方

Question

只是想知道在 Python 中生成列表的所有循环移位的最有效方法是什么。在任何一个方向。例如，给定一个列表 [1, 2, 3, 4]，我想生成:

[[1, 2, 3, 4],
 [4, 1, 2, 3],
 [3, 4, 1, 2],
 [2, 3, 4, 1]]

下一个排列是通过将最后一个元素移到前面生成的，或者:

[[1, 2, 3, 4],
 [2, 3, 4, 1],
 [3, 4, 1, 2],
 [4, 1, 2, 3]]

下一个排列是通过将第一个元素移到后面生成的。

第二种情况对我来说稍微更有趣一些，因为它会导致减少拉丁方(第一种情况也会给出拉丁方，只是没有减少)，这就是我试图用来进行实验性 block 设计的方法。它实际上与第一种情况并无太大不同，因为它们只是彼此重新排序，但顺序仍然很重要。

第一种情况我目前的实现是:

def gen_latin_square(mylist):
    tmplist = mylist[:]
    latin_square = []
    for i in range(len(mylist)):
        latin_square.append(tmplist[:])
        tmplist = [tmplist.pop()] + tmplist
    return latin_square

对于第二种情况:

def gen_latin_square(mylist):
    tmplist = mylist[:]
    latin_square = []
    for i in range(len(mylist)):
        latin_square.append(tmplist[:])
        tmplist = tmplist[1:] + [tmplist[0]]
    return latin_square

第一种情况对我来说似乎应该相当有效，因为它使用 pop()，但在第二种情况下你不能这样做，所以我想听听想法关于如何更有效地做到这一点。也许 itertools 中的某些东西会有所帮助？或者可能是第二种情况的双端队列？

Answer 1

你可以使用 collections.deque:

from collections import deque

g = deque([1, 2, 3, 4])

for i in range(len(g)):
    print list(g) #or do anything with permutation
    g.rotate(1) #for right rotation
    #or g.rotate(-1) for left rotation

它打印:

 [1, 2, 3, 4]
 [4, 1, 2, 3]
 [3, 4, 1, 2]
 [2, 3, 4, 1]

要将其更改为向左旋转，只需将 g.rotate(1) 替换为 g.rotate(-1)。