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

[Steven D'Aprano]

On Sun, 2 Aug 2015 08:51 am, Lukas Barth wrote:

> On Saturday, August 1, 2015 at 11:37:48 PM UTC+2, Emile van Sebille wrote:
>> Well, it looks to me that I don't know what a 'canonical rotation' is --
> 
> That's because it is not defined. ;)
> 
> I need a way to rotate one of these lists in a way so that it will produce
> the same output every time, regardless of what the input rotation was.

I'm not convinced that you necessarily do, but for the sake of the argument
suppose you do...

> Example:
> 
> [0,1,2,3,4] => [0,1,2,3,4]
> [2,3,4,0,1] => [0,1,2,3,4]
> [3,4,0,1,2] => [0,1,2,3,4]
> ...

How is this different from sorted(the_list)?

Ah, wait, I've just answered my own question... 

[0,1,2,4,3] != [0,1,2,3,4]


> It doesn't have to be "[0,1,2,3,4]", it can just as well be [2,3,4,1,0],
> as long as it's always the same.

Keep a cache, and intern the first seen version of the list in the cache.

CACHE = {}

def intern(alist):
    t = MyTuple(alist)
    if t not in CACHE:
        CACHE[t] = alist
    return CACHE[t]

    
# Untested
class MyTuple(tuple):
    def __eq__(self, other):
        if self is other:  return True
        if not isinstance(other, MyTuple):  return NotImplemented
        if len(self) != len(other):  return False
        d = self+self
        return other in d
    def __hash__(self):
        return hash(frozenset(self))



-- 
Steven