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,开发者_如何学C 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?
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)
.
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.
variation on slicing "conservation law" 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]]
more_itertools
is a third-party library that offers a tool for cyclic permutations:
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)]
See also Wikipedia:
A circular shift is a special kind of cyclic permutation, which in turn is a special kind of permutation.
The answer by @Bruno Lenzi does not seem to work:
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']]
I give a correct version below, however the solution by @f5r5e5d is faster.
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
I removed the print statement in use_cycle
and use_slice
for timing purposes.
Using itertools to avoid indexing:
x = itertools.cycle(a)
[[x.next() for i in a] for j in a]
This will be my solution.
#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
This will output the following:
[4, 1, 2, 3]
[3, 4, 1, 2]
[2, 3, 4, 1]
[1, 2, 3, 4]
You can also use pop
instead of using list slicing but the problem with pop
is that it will return something.
Also the above code will work for any length of list. I have not checked for performance of the code. I am assuming that it will work better.
You should have a look at Python docs for getting a good understanding of List slicing.
精彩评论