Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #94888

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

Show key headers only | View raw

Lukas Barth <mail@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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Most pythonic way of rotating a circular list to a canonical point Lukas Barth <mail@tinloaf.de> - 2015-08-01 13:34 -0700
  Re: Most pythonic way of rotating a circular list to a canonical point Emile van Sebille <emile@fenx.com> - 2015-08-01 13:49 -0700
    Re: Most pythonic way of rotating a circular list to a canonical point Lukas Barth <mail@tinloaf.de> - 2015-08-01 14:12 -0700
      Re: Most pythonic way of rotating a circular list to a canonical point Emile van Sebille <emile@fenx.com> - 2015-08-01 14:29 -0700
  Re: Most pythonic way of rotating a circular list to a canonical point Marko Rauhamaa <marko@pacujo.net> - 2015-08-01 23:57 +0300
    Re: Most pythonic way of rotating a circular list to a canonical point Lukas Barth <mail@tinloaf.de> - 2015-08-01 14:04 -0700
      Re: Most pythonic way of rotating a circular list to a canonical point Lukas Barth <mail@tinloaf.de> - 2015-08-01 16:32 -0700
      Re: Most pythonic way of rotating a circular list to a canonical point Marko Rauhamaa <marko@pacujo.net> - 2015-08-02 09:25 +0300
  Re: Most pythonic way of rotating a circular list to a canonical point Lukas Barth <mail@tinloaf.de> - 2015-08-01 14:24 -0700
    Re: Most pythonic way of rotating a circular list to a canonical point Emile van Sebille <emile@fenx.com> - 2015-08-01 14:36 -0700
      Re: Most pythonic way of rotating a circular list to a canonical point Lukas Barth <mail@tinloaf.de> - 2015-08-01 15:51 -0700
        Re: Most pythonic way of rotating a circular list to a canonical point Joel Goldstick <joel.goldstick@gmail.com> - 2015-08-01 18:58 -0400
        Re: Most pythonic way of rotating a circular list to a canonical point Josh English <Joshua.R.English@gmail.com> - 2015-08-01 16:43 -0700
        Re: Most pythonic way of rotating a circular list to a canonical point Steven D'Aprano <steve@pearwood.info> - 2015-08-02 18:17 +1000
    Re: Most pythonic way of rotating a circular list to a canonical point Paul Rubin <no.email@nospam.invalid> - 2015-08-01 14:43 -0700
      Re: Most pythonic way of rotating a circular list to a canonical point Lukas Barth <mail@tinloaf.de> - 2015-08-01 15:53 -0700
        Re: Most pythonic way of rotating a circular list to a canonical point Paul Rubin <no.email@nospam.invalid> - 2015-08-01 19:47 -0700
          Re: Most pythonic way of rotating a circular list to a canonical point Paul Rubin <no.email@nospam.invalid> - 2015-08-01 20:02 -0700
    Re: Most pythonic way of rotating a circular list to a canonical point Cameron Simpson <cs@zip.com.au> - 2015-08-02 08:25 +1000
      Re: Most pythonic way of rotating a circular list to a canonical point Lukas Barth <mail@tinloaf.de> - 2015-08-01 15:55 -0700
        Re: Most pythonic way of rotating a circular list to a canonical point Cameron Simpson <cs@zip.com.au> - 2015-08-02 11:20 +1000
  Re: Most pythonic way of rotating a circular list to a canonical point wolfram.hinderer@googlemail.com - 2015-08-01 17:07 -0700
  Re: Most pythonic way of rotating a circular list to a canonical point pavlovevidence@gmail.com - 2015-08-02 03:51 -0700
  Re: Most pythonic way of rotating a circular list to a canonical point Tim Chase <python.list@tim.thechases.com> - 2015-08-02 13:19 -0500
  Re: Most pythonic way of rotating a circular list to a canonical point Larry Hudson <orgnut@yahoo.com> - 2015-08-02 13:01 -0700
    Re: Most pythonic way of rotating a circular list to a canonical point Joonas Liik <liik.joonas@gmail.com> - 2015-08-02 23:58 +0300
      Re: Most pythonic way of rotating a circular list to a canonical point Larry Hudson <orgnut@yahoo.com> - 2015-08-03 12:56 -0700
    Re: Most pythonic way of rotating a circular list to a canonical point Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-08-03 15:19 +0100

csiph-web