在Python中生成循环移位/缩小的拉丁方 [英] Generating circular shifts / reduced Latin Squares in Python

问题描述

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

Was just wondering what's the most efficient way of generating all the circular shifts of a list in Python. In either direction. For example, given a list [1, 2, 3, 4], I want to generate either:

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

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

where the next permutation is generated by moving the last element to the front, or:

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

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

where the next permutation is generated by moving the first element to the back.

第二种情况对我来说有点有趣，因为这会导致减小的拉丁方(第一种情况也给出了一个拉丁方，只是没有减小)，这就是我正在尝试进行实验性块设计的方法.实际上，它们与第一种情况并没有什么不同，因为它们只是彼此重新排序，但是顺序仍然很重要.

The second case is slightly more interesting to me because it results in a reduced Latin square (the first case also gives a Latin square, just not reduced), which is what I'm trying to use to do experimental block design. It actually isn't that different from the first case since they're just re-orderings of each other, but order does still matter.

我在第一种情况下的当前实现是:

The current implementation I have for the first case is:

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中有一些有用的东西?也许第二种情况是双头队列?

The first case seems like it should be reasonably efficient to me, since it uses pop(), but you can't do that in the second case, so I'd like to hear ideas about how to do this more efficiently. Maybe there's something in itertools that will help? Or maybe a double-ended queue for the second case?

推荐答案

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

For the first part, the most concise way probably is

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

尽管我没有做任何计时，但这些代码也应该比您的代码更有效.

These should also be much more efficient than your code, though I did not do any timings.

这篇关于在Python中生成循环移位/缩小的拉丁方的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！