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

Answer 4

more_itertools 是一个第三方库，提供了一个工具< a href="https://more-itertools.readthedocs.io/en/latest/api.html#more_itertools.circular_shifts" rel="nofollow noreferrer">循环排列：

import more_itertools as mit


mit.circular_shifts(range(1, 5))
# [(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)]

另请参阅 维基百科：

循环移位是一种特殊的循环排列，而循环排列又是一种特殊的排列。

Answer 5

@Bruno Lenzi 的答案似乎不起作用：

In [10]: from itertools import cycle

In [11]: x = cycle('ABCD')

In [12]: print [[x.next() for _ in range(4)] for _ in range(4)]
[['A', 'B', 'C', 'D'], ['A', 'B', 'C', 'D'], ['A', 'B', 'C', 'D'], ['A', 'B', 'C', 'D']]

我在下面给出了正确的版本，但是 @f5r5e5d 的解决方案更快。

In [45]: def use_cycle(a):
    x=cycle(a)
    for _ in a:
        x.next()
        print [x.next() for _ in a]
   ....:         

In [46]: use_cycle([1,2,3,4])
[2, 3, 4, 1]
[3, 4, 1, 2]
[4, 1, 2, 3]
[1, 2, 3, 4]

In [50]: def use_slice(a):
    print [ a[n:] + a[:n] for n in range(len(a)) ]
  ....:     

In [51]: use_slice([1,2,3,4])
[[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]

In [54]: timeit.timeit('use_cycle([1,2,3,4])','from __main__ import use_cycle',number=100000)
Out[54]: 0.4884989261627197

In [55]: timeit.timeit('use_slice([1,2,3,4])','from __main__ import use_slice',number=100000)
Out[55]: 0.3103291988372803

In [58]: timeit.timeit('use_cycle([1,2,3,4]*100)','from __main__ import use_cycle',number=100)
Out[58]: 2.4427831172943115

In [59]: timeit.timeit('use_slice([1,2,3,4]*100)','from __main__ import use_slice',number=100)
Out[59]: 0.12029695510864258

出于计时目的，我删除了 use_cycle 和 use_slice 中的打印语句。

Answer 6

使用 itertools 避免索引：

x = itertools.cycle(a)
[[x.next() for i in a] for j in a]

Answer 7

这将是我的解决方案。

#given list
a = [1,2,3,4]
#looping through list
for i in xrange(len(a)):
    #inserting last element at the starting
    a.insert(0,a[len(a)-1])
    #removing the last element
    a = a[:len(a)-1]
    #printing if you want to
    print a

这将输出以下内容：

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

您还可以使用 pop 而不是使用列表切片，但 pop 的问题是它会返回一些内容。

另外，上面的代码适用于任何长度的列表。我还没有检查代码的性能。我假设它会工作得更好。

您应该查看 Python 文档 以更好地理解列表切片。