在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

这是一个关于切片的变体，涉及到“守恒定律”。这里的代码 a = a[:i] + a[i:] 的意思是，把列表或字符串 a 从头到第 i 个位置切开，然后再把第 i 个位置到最后的部分拼接起来。简单来说，就是把 a 分成两部分，然后把这两部分合在一起。

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

Answer 2

你可以使用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 3

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

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

这些方法的效率应该比你的代码高很多，虽然我没有进行时间测试。