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

Marko Rauhamaa marko at pacujo.net
Sun Aug 2 08:25:56 CEST 2015


Lukas Barth <mail at tinloaf.de>:

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

First, lists can't be used as dict keys, but that minor point is easy to
overcome.

Secondly, a hash doesn't need to be unique, it's enough for it to be
discerning. So you could, for example, choose:

   sum([ hash(x) for x in L ]) + hash(sum(L))

That doesn't discern any permutations, but depending on your application
might be good enough.

That way, you use the "pretty good" hash function together with the
circular equality test and you won't be needing any canonical
representation for the key.


Marko


More information about the Python-list mailing list