<p dir="ltr"><br>
</p>
<p dir="ltr"></p>
<p dir="ltr">On Sun, 2 Aug 2015 00:05 Oscar Benjamin <<a href="mailto:oscar.j.benjamin@gmail.com">oscar.j.benjamin@gmail.com</a>> wrote:</p>
<blockquote><p dir="ltr"><br>
On Sat, 1 Aug 2015 22:06 Lukas Barth <<a href="mailto:mail@tinloaf.de">mail@tinloaf.de</a>> wrote:<br></p>
</blockquote>
<blockquote><blockquote><p dir="ltr"><br>
Nice idea! But I actually really need those "canonic rotations", since I'm hashing them somewhere.<br>
</p>
</blockquote>
</blockquote>
<blockquote><p dir="ltr"><br></p>
<p dir="ltr">Do you really need the canonical rotation or just a hash that is invariant under rotations?</p>
<p dir="ltr">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.<br>
</p>
</blockquote>
<blockquote><p dir="ltr"><br>
</p>
</blockquote>
<p dir="ltr"><br>
I said "least common" but meant "minimum". A potential improvement would be to use the minimum element of the least common elements instead of just the minimum element. Presumably in most cases there would be at least some unique elements so if you take the minimum of those then you would only need to compute 1 sequence hash. Maybe this is unnecessary though.</p>
<p dir="ltr">--<br>
Oscar </p>
<p dir="ltr"><br>
</p>