Most pythonic way of rotating a circular list to a canonical point
cs at zip.com.au
Sun Aug 2 03:20:57 CEST 2015
On 01Aug2015 15:55, Lukas Barth <mail at tinloaf.de> wrote:
>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.
>> 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..
Are you collating on the hash before doing anything? I think I may have missed
part of your problem specification. I thought you had a list and needed to
recognise other lists which were rotations of it, and possibly return them pre
or post rotation.
If you're hashing the first list I'm presuming you're using that to allocate it
to a bucket (even notionally) to avoid wasting time comparing it against wildly
different lists, just compare against likely matches? Or what?
If that is the case, choose a hash function that: is affected by the list
length and is independent of the list item ordering. That is easy to arrange
and is guarrenteed that a rotated version of the list will have the same hash.
Trivial hash function: sum(list1)+len(list1)
It is simple and will work. It has downsides that might be a problem in other
contexts, but since I don't know what you're using the hash for then I can
Remember, hash functions are arbitrary - they just have to obey particular
constraints dictated by your needs.
Cameron Simpson <cs at zip.com.au>
More information about the Python-list