Most pythonic way of rotating a circular list to a canonical point

[pavlovevidence at gmail.com]

On Saturday, August 1, 2015 at 1:34:44 PM UTC-7, Lukas Barth wrote:
> Hi!
> 
> I have a list of numbers that I treat as "circular", i.e. [1,2,3] and [2,3,1] should be the same. Now I want to rotate these to a well defined status, so that I can can compare them.
> 
> If all elements are unique, the solution is easy: find the minimum element, find its index, then use mylist[:index] + mylist[index:], i.e. the minimum element will always be at the beginning.
> 
> But say I have [0,1,0,2,0,3]. I can in fact guarantee that no *pair* will appear twice in that list, i.e. I could search for the minimum, if that is unique go on as above, otherwise find *all* positions of the minimum, see which is followed by the smallest element, and then rotate that position to the front.
> 
> Now that seems an awful lot of code for a (seemingly?) simple problem. Is there a nice, pythonic way to do this?
> 
> Thanks for enlightening me!

[[[Warning: all code untested, sorry!]]]

The general problem (no assumptions about the items in the list except that they're all sortable together) is interesting.  It doesn't seem like a simple one to me at all.  An acceptable criterion would be if you took the lexically smallest value of every rotation of the list; that would yield the same result for every initial rotation.  You can do it in like this:

    anchor = min(range(len(X)),key=lambda i:X[i:]+X[:i])
    canonical_X = X[anchor:]+X[:anchor]

I doubt this would be that efficient, though, since it happens to construct every single rotation in the process of scanning.  However, you'll notice that the minimum lexical value can only occur when the starting point is the minimum value in the list, so you can almost certainly improve performace to find all the minimum values and only test those rotations, especially if the number of minima is small compared to the list size.  (However, be sure to timeit for actual evidence rather than my guessing.)

    min_value = min(X)
    i = X.index(min_value)
    while True:
        start_points.append(i)
        try:
            i = X.index(min_value,i+1)
        except ValueError:
            break
    anchor = min(start_points,key=lambda i:X[i:]+X[:i])
    canonical_X = X[anchor:]+X[:anchor]



Your lists aren't arbitrary, however and they actually seem to be ordered pairs (in which case the first question I have is why not have it be a list of 2-tuples? but I can imagine a few reasons).  You say the pairs are known to be unique, so all you have to do is find the index of the minimum pair.  One can use zip and slicing to generate 2-tuples from the flat list, whence you can find the minimum.

    pairs = list(zip(X[0::2],X[1::2]))
    min_pair = min(pairs)
    anchor = 2 * pairs.index(min_pair)
    canonical_X = X[anchor:]+X[:anchor]


Carl Banks