Most pythonic way of rotating a circular list to a canonical point
Marko Rauhamaa
marko at pacujo.net
Sun Aug 2 02:25:56 EDT 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