Generating cyclic permutations / reduced Latin Squares in Python
Question: 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?


Answer: 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)`.

