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

通过将第一个元素移动到后面来生成下一个排列.

第二种情况对我来说稍微有些意思,因为它导致拉丁方形减少(第一种情况也给出拉丁方,只是没有减少),这正是我试图用来做实验块设计的.它实际上与第一种情况没有什么不同,因为它们只是彼此重新排序,但顺序仍然很重要.

我对第一种情况的当前实施是:

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

Answer 2

对于第一部分,最简洁的方法可能是

a = [1, 2, 3, 4]
n = len(a)
[[a[i - j] for i in range(n)] for j in range(n)]
# [[1, 2, 3, 4], [4, 1, 2, 3], [3, 4, 1, 2], [2, 3, 4, 1]]

而对于第二部分

[[a[i - j] for i in range(n)] for j in range(n, 0, -1)]
# [[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]

这些也应该比你的代码更有效,尽管我没有做任何时间安排.

Answer 3

切片“守恒定律”的变化 a = a[:i] + a[i:]

ns = list(range(5))
ns
Out[34]: [0, 1, 2, 3, 4]

[ns[i:] + ns[:i] for i in range(len(ns))]
Out[36]: 
[[0, 1, 2, 3, 4],
 [1, 2, 3, 4, 0],
 [2, 3, 4, 0, 1],
 [3, 4, 0, 1, 2],
 [4, 0, 1, 2, 3]]


[ns[-i:] + ns[:-i] for i in range(len(ns))]
Out[38]: 
[[0, 1, 2, 3, 4],
 [4, 0, 1, 2, 3],
 [3, 4, 0, 1, 2],
 [2, 3, 4, 0, 1],
 [1, 2, 3, 4, 0]]