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

Cameron Simpson 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.
>
>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..

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 
address that.

Remember, hash functions are arbitrary - they just have to obey particular 
constraints dictated by your needs.

Comments?

Cheers,
Cameron Simpson <cs at zip.com.au>


More information about the Python-list mailing list