Most pythonic way of rotating a circular list to a canonical point
Hi! 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! Lukas -- https://mail.python.org/mailman/listinfo/python-list
Re: Most pythonic way of rotating a circular list to a canonical point
On Saturday, August 1, 2015 at 10:57:19 PM UTC+2, Marko Rauhamaa wrote: > > def circularly_equal(l1, l2): > length = len(l1) > if length != len(l2): > return False > twice = l1 + l1 > for i in range(length): > if twice[i:i + length] == l2: > return True > return False > Nice idea! But I actually really need those "canonic rotations", since I'm hashing them somewhere.. Lukas -- https://mail.python.org/mailman/listinfo/python-list
Re: Most pythonic way of rotating a circular list to a canonical point
On Saturday, August 1, 2015 at 10:51:03 PM UTC+2, Emile van Sebille wrote: > Is the problem to determine if one list of circular numbers 'matches' > another one despite rotation status? If so, I'd do something like: Well.. no. I actually really need this "canonical" rotation, since I'm hashing this, returning it to other parts of the software, etc.. But thanks! Lukas -- https://mail.python.org/mailman/listinfo/python-list
Re: Most pythonic way of rotating a circular list to a canonical point
Perhaps I should clarify a bit: - I definitely need a "canonical rotation" - just a comparison result is not enough - It does not matter what that rotation is. Starting with the smallest element was just an idea by me, any rotation that can easily produced will do. -- https://mail.python.org/mailman/listinfo/python-list
Re: Most pythonic way of rotating a circular list to a canonical point
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? Thanks a lot, Lukas -- https://mail.python.org/mailman/listinfo/python-list
Re: Most pythonic way of rotating a circular list to a canonical point
On Saturday, August 1, 2015 at 11:43:28 PM UTC+2, Paul Rubin wrote: > How large are these lists supposed to be? Potentially large. Not so large though that iterating them (multiple times) should be a problem. > [Concatenated Hashes] > > If the lists are very large that doesn't sound so great due to storage > requirements.. Also, that still doesn't compute that one "canonical ordering"... Thanks, Lukas -- https://mail.python.org/mailman/listinfo/python-list
Re: Most pythonic way of rotating a circular list to a canonical point
On Sunday, August 2, 2015 at 12:32:25 AM UTC+2, Cameron Simpson wrote: > Fine. This also eliminates any solution which just computes a hash. Exactly. > Might I suggest instead simply starting with the leftmost element in the > first > list; call this elem0. Then walk the second list from 0 to len(list2). If > that > element equals elem0, _then_ compare the list at that point as you suggested. > > Is there an aspect of this which doesn't work? The problem is: When I compute a hash over list1 (in its canonical form), I do not yet know list2 (or list3, or listN...) against which they will be compared later.. Lukas -- https://mail.python.org/mailman/listinfo/python-list
Re: Most pythonic way of rotating a circular list to a canonical point
On Sunday, August 2, 2015 at 1:05:32 AM UTC+2, Oscar Benjamin wrote: > Do you really need the canonical rotation or just a hash that is invariant > under rotations? Having that canonical rotation would make the code simpler and faster, probably, but a rotationally invariant hash is a good start. > I don't know of a solution to the former that is better than what you already > have but the latter is an easier problem: Find the minimum element. Compute > the hash of the rotated sequence for each occurrence of the least common > element. Add those hashes together or multiply them or some similar > operation. That's your hash that will compare equal for any rotation of a > given sequence. Yes, that sounds like an idea if I decide to just go with the hash. Thanks! Lukas -- https://mail.python.org/mailman/listinfo/python-list
