Most pythonic way of rotating a circular list to a canonical point
orgnut at yahoo.com
Sun Aug 2 22:01:40 CEST 2015
On 08/01/2015 01:34 PM, Lukas Barth wrote:
> 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!
Let me try to re-state what I see is your actual problem. (Of course I could be wrong...) ;-)
Most of the answers you have been getting concentrate on comparisons and hashes, but those are
irrelevant to your need -- they come later. What you are trying to do is to uniquely and
independently determine the "starting point" for the rotation. That is, which element will be
rotated to index 0. Using the minimum is possible, but that fails if that minimum appears more
than once in the list -- it does not give a unique solution.
For a specific example... if you are given any _one_ of these lists:
[1, 5, 0, 3, 0], [5, 0, 3, 0, 1], [0, 3, 0, 1, 5], [3, 0, 1, 5, 0], [0, 1, 5, 0, 3]
it can be _independently_ rotated to (for example) [3, 0, 1, 5, 0]
That example does not use the minimum as the starting point, but how the starting point can be
absolutely and uniquely determined is your fundamental problem. I do not have an answer for
that. But I thought this might be a clearer description of what I think you are really looking for.
I hope I'm right. ;-) Good luck.
-=- Larry -=-
More information about the Python-list