Most pythonic way of rotating a circular list to a canonical point
Steven D'Aprano
steve at pearwood.info
Sun Aug 2 04:17:42 EDT 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
More information about the Python-list
mailing list