Generating cyclic permutations / reduced Latin Squares in Python
Was just wondering what's the most efficient way of generating all the cyclic permutations 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
For the second case its:
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
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]]
and for the second part
[[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.
You can use 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
It prints:
[1, 2, 3, 4]
[4, 1, 2, 3]
[3, 4, 1, 2]
[2, 3, 4, 1]
To change it for left rotation just replace g.rotate(1) with g.rotate(-1) .
切片“保守法则” a = a[:i] + a[i:]变化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]]
上一篇: 生成一组排列（最有效）