On 01Aug2015 15:55, Lukas Barth <m...@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 <c...@zip.com.au>
--
https://mail.python.org/mailman/listinfo/python-list

Reply via email to