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

Steven D'Aprano steve at pearwood.info
Sun Aug 2 10:17:42 CEST 2015

```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

```