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

Josh English Joshua.R.English at gmail.com
Sun Aug 2 01:43:44 CEST 2015


On Saturday, August 1, 2015 at 3:52:25 PM UTC-7, 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.
> 
> 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]
> ...
> 
> 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.
> 
> Did that make it clearer?
> 

Is this "canoncal rotation" different than sorting. I think you mean it to be, but these examples all look like sorting to me.

I think the collections.deque object has a rotate method, and rotating through the possibilities looking for matches may work, or take any deque, rotate so the minimum value is at the first place in the deque, and then compare.

Or am I not understanding what you mean?

Josh



More information about the Python-list mailing list