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

Groups > comp.lang.python > #94860 > unrolled thread

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

Back to article view | Back to comp.lang.python

Contents

  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

Page 1 of 2  [1] 2  Next page →

#94860 — Most pythonic way of rotating a circular list to a canonical point

Hi!

I have a list of numbers that I treat as "circular", i.e. [1,2,3] and [2,3,1] should be the same. Now I want to rotate these to a well defined status, so that I can can compare them.

If all elements are unique, the solution is easy: find the minimum element, find its index, then use mylist[:index] + mylist[index:], i.e. the minimum element will always be at the beginning.

But say I have [0,1,0,2,0,3]. I can in fact guarantee that no *pair* will appear twice in that list, i.e. I could search for the minimum, if that is unique go on as above, otherwise find *all* positions of the minimum, see which is followed by the smallest element, and then rotate that position to the front.

Now that seems an awful lot of code for a (seemingly?) simple problem. Is there a nice, pythonic way to do this?

Thanks for enlightening me!

Lukas

[toc] | [next] | [standalone]

#94861

On 8/1/2015 1:34 PM, Lukas Barth wrote:
> Hi!
>
> I have a list of numbers that I treat as "circular", i.e. [1,2,3] and [2,3,1] should be the same. Now I want to rotate these to a well defined status, so that I can can compare them.
>
> If all elements are unique, the solution is easy: find the minimum element, find its index, then use mylist[:index] + mylist[index:], i.e. the minimum element will always be at the beginning.
>
> But say I have [0,1,0,2,0,3]. I can in fact guarantee that no *pair* will appear twice in that list, i.e. I could search for the minimum, if that is unique go on as above, otherwise find *all* positions of the minimum, see which is followed by the smallest element, and then rotate that position to the front.
>
> Now that seems an awful lot of code for a (seemingly?) simple problem. Is there a nice, pythonic way to do this?

Well, I have not understood the problem for such a seemingly simple one.  :)

Is the problem to determine if one list of circular numbers 'matches' 
another one despite rotation status?  If so, I'd do something like:

def matchcircularlists(L1,L2):
     #return True if L1 is a rotation variant of L2
     return "".join(map(str,L1)) in "".join(map(str,L2+L2))

Emile

[toc] | [prev] | [next] | [standalone]

#94865

On Saturday, August 1, 2015 at 10:51:03 PM UTC+2, Emile van Sebille wrote:
> Is the problem to determine if one list of circular numbers 'matches' 
> another one despite rotation status?  If so, I'd do something like:

Well.. no. I actually really need this "canonical" rotation, since I'm hashing this, returning it to other parts of the software, etc..

But thanks!

Lukas

[toc] | [prev] | [next] | [standalone]

#94867

On 8/1/2015 2:12 PM, Lukas Barth wrote:
> On Saturday, August 1, 2015 at 10:51:03 PM UTC+2, Emile van Sebille wrote:
>> Is the problem to determine if one list of circular numbers 'matches'
>> another one despite rotation status?  If so, I'd do something like:
>
> Well.. no. I actually really need this "canonical" rotation, since I'm hashing this, returning it to other parts of the software, etc..

Then I'm not sure that I understand what exactly the problem is.  Can 
you state it in terms of what you start with and what you expect to get?

The only clue I see is "Now I want to rotate these to a well defined 
status, so that I can can compare them."  Which is where I understood 
you to want to compare them.

You might check at http://www.catb.org/esr/faqs/smart-questions.html

Emile

[toc] | [prev] | [next] | [standalone]

#94862

Lukas Barth <mail@tinloaf.de>:

> I have a list of numbers that I treat as "circular", i.e. [1,2,3] and
> [2,3,1] should be the same. Now I want to rotate these to a well defined
> status, so that I can can compare them.
>
> If all elements are unique, the solution is easy: find the minimum
> element, find its index, then use mylist[:index] + mylist[index:], i.e.
> the minimum element will always be at the beginning.
>
> But say I have [0,1,0,2,0,3]. I can in fact guarantee that no *pair*
> will appear twice in that list, i.e. I could search for the minimum, if
> that is unique go on as above, otherwise find *all* positions of the
> minimum, see which is followed by the smallest element, and then rotate
> that position to the front.
>
> Now that seems an awful lot of code for a (seemingly?) simple problem.
> Is there a nice, pythonic way to do this?

How about:

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


Marko

[toc] | [prev] | [next] | [standalone]

#94864

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

Lukas

[toc] | [prev] | [next] | [standalone]

#94876

On Sunday, August 2, 2015 at 1:05:32 AM UTC+2, Oscar Benjamin wrote:
> Do you really need the canonical rotation or just a hash that is invariant under rotations?

Having that canonical rotation would make the code simpler and faster, probably, but a rotationally invariant hash is a good start.

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

Yes, that sounds like an idea if I decide to just go with the hash. Thanks!

Lukas

[toc] | [prev] | [next] | [standalone]

#94888

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

[toc] | [prev] | [next] | [standalone]

#94866

Perhaps I should clarify a bit:

- I definitely need a "canonical rotation" - just a comparison result is not enough

- It does not matter what that rotation is. Starting with the smallest element was just an idea by me, any rotation that can easily produced will do.

[toc] | [prev] | [next] | [standalone]

#94868

On 8/1/2015 2:24 PM, Lukas Barth wrote:
> Perhaps I should clarify a bit:
>
> - I definitely need a "canonical rotation" - just a comparison result is not enough

Well, it looks to me that I don't know what a 'canonical rotation' is -- 
there's no wikipedia article and googling yields all sorts of 
specialized math related articles.

Sorry,

[toc] | [prev] | [next] | [standalone]

#94871

On Saturday, August 1, 2015 at 11:37:48 PM UTC+2, Emile van Sebille wrote:
> Well, it looks to me that I don't know what a 'canonical rotation' is -- 

That's because it is not defined. ;)

I need a way to rotate one of these lists in a way so that it will produce the same output every time, regardless of what the input rotation was.

Example:

[0,1,2,3,4] => [0,1,2,3,4]
[2,3,4,0,1] => [0,1,2,3,4]
[3,4,0,1,2] => [0,1,2,3,4]
...

It doesn't have to be "[0,1,2,3,4]", it can just as well be [2,3,4,1,0], as long as it's always the same.

Did that make it clearer?

Thanks a lot,

Lukas

[toc] | [prev] | [next] | [standalone]

#94874

On Sat, Aug 1, 2015 at 6:51 PM, Lukas Barth <mail@tinloaf.de> wrote:
> On Saturday, August 1, 2015 at 11:37:48 PM UTC+2, Emile van Sebille wrote:
>> Well, it looks to me that I don't know what a 'canonical rotation' is --
>
> That's because it is not defined. ;)
>
> I need a way to rotate one of these lists in a way so that it will produce the same output every time, regardless of what the input rotation was.
>
> Example:
>
> [0,1,2,3,4] => [0,1,2,3,4]
> [2,3,4,0,1] => [0,1,2,3,4]
> [3,4,0,1,2] => [0,1,2,3,4]
> ...
>
> It doesn't have to be "[0,1,2,3,4]", it can just as well be [2,3,4,1,0], as long as it's always the same.
>
> Did that make it clearer?
>
> Thanks a lot,
>
> Lukas

I've been following along.  The early suggestion to double one list
and see if the second list is in the double list seems to prove they
are the same -- one is just rotated to a different starting point.  I
don't understand the term 'canonical' in this example, but what is it
that the solution given doesn't provide for you?

-- 
Joel Goldstick
http://joelgoldstick.com

[toc] | [prev] | [next] | [standalone]

#94877

On Saturday, August 1, 2015 at 3:52:25 PM UTC-7, Lukas Barth wrote:
> On Saturday, August 1, 2015 at 11:37:48 PM UTC+2, Emile van Sebille wrote:
> > Well, it looks to me that I don't know what a 'canonical rotation' is -- 
> 
> That's because it is not defined. ;)
> 
> I need a way to rotate one of these lists in a way so that it will produce the same output every time, regardless of what the input rotation was.
> 
> Example:
> 
> [0,1,2,3,4] => [0,1,2,3,4]
> [2,3,4,0,1] => [0,1,2,3,4]
> [3,4,0,1,2] => [0,1,2,3,4]
> ...
> 
> It doesn't have to be "[0,1,2,3,4]", it can just as well be [2,3,4,1,0], as long as it's always the same.
> 
> Did that make it clearer?
> 

Is this "canoncal rotation" different than sorting. I think you mean it to be, but these examples all look like sorting to me.

I think the collections.deque object has a rotate method, and rotating through the possibilities looking for matches may work, or take any deque, rotate so the minimum value is at the first place in the deque, and then compare.

Or am I not understanding what you mean?

Josh

[toc] | [prev] | [next] | [standalone]

#94892

On Sun, 2 Aug 2015 08:51 am, Lukas Barth wrote:

> On Saturday, August 1, 2015 at 11:37:48 PM UTC+2, Emile van Sebille wrote:
>> Well, it looks to me that I don't know what a 'canonical rotation' is --
> 
> That's because it is not defined. ;)
> 
> I need a way to rotate one of these lists in a way so that it will produce
> the same output every time, regardless of what the input rotation was.

I'm not convinced that you necessarily do, but for the sake of the argument
suppose you do...

> Example:
> 
> [0,1,2,3,4] => [0,1,2,3,4]
> [2,3,4,0,1] => [0,1,2,3,4]
> [3,4,0,1,2] => [0,1,2,3,4]
> ...

How is this different from sorted(the_list)?

Ah, wait, I've just answered my own question... 

[0,1,2,4,3] != [0,1,2,3,4]


> It doesn't have to be "[0,1,2,3,4]", it can just as well be [2,3,4,1,0],
> as long as it's always the same.

Keep a cache, and intern the first seen version of the list in the cache.

CACHE = {}

def intern(alist):
    t = MyTuple(alist)
    if t not in CACHE:
        CACHE[t] = alist
    return CACHE[t]

    
# Untested
class MyTuple(tuple):
    def __eq__(self, other):
        if self is other:  return True
        if not isinstance(other, MyTuple):  return NotImplemented
        if len(self) != len(other):  return False
        d = self+self
        return other in d
    def __hash__(self):
        return hash(frozenset(self))



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#94869

Lukas Barth <mail@tinloaf.de> writes:
> - It does not matter what that rotation is. Starting with the smallest
> element was just an idea by me, any rotation that can easily produced
> will do.

How large are these lists supposed to be?  If they're (say) 5 elements,
you could make the hash code consist of the concatenated hashes of each
of the 5 rotations, or maybe a Bloom filter on those hashes.  Then to do
a lookup, hash your target list and see if it appears in the table.

If the lists are very large that doesn't sound so great due to storage
requirements..

[toc] | [prev] | [next] | [standalone]

#94872

On Saturday, August 1, 2015 at 11:43:28 PM UTC+2, Paul Rubin wrote:
> How large are these lists supposed to be? 

Potentially large. Not so large though that iterating them (multiple times) should be a problem.

> [Concatenated Hashes]
> 
> If the lists are very large that doesn't sound so great due to storage
> requirements..

Also, that still doesn't compute that one "canonical ordering"...

Thanks,

Lukas

[toc] | [prev] | [next] | [standalone]

#94883

Lukas Barth <mail@tinloaf.de> writes:
>> [Concatenated Hashes]
> Also, that still doesn't compute that one "canonical ordering"...

It was intended to get rid of the need.  What is the actual application?

How does this sound?  To circularly hash [a,b,c,d] use:

  H([b-a, c-b, d-c, a-d])

where H is your favorite hash function on a list of that element type.
That should give the same hash value for any rotation of the list.
It generalizes in the obvious way to other lengths.

[toc] | [prev] | [next] | [standalone]

#94884

Paul Rubin <no.email@nospam.invalid> writes:
>   H([b-a, c-b, d-c, a-d])
> where H is your favorite hash function on a list of that element type.

I wrote that up unclearly.  H is supposed to be a hash on one element,
and then you combine H(b-a), H(c-b), etc. in a commutative way, such as
by adding them.  Still not sure if this works though.

[toc] | [prev] | [next] | [standalone]

#94870

On 01Aug2015 14:24, Lukas Barth <mail@tinloaf.de> wrote:
>Perhaps I should clarify a bit:
>- I definitely need a "canonical rotation" - just a comparison result is not enough

Fine. This also eliminates any solution which just computes a hash.

>- It does not matter what that rotation is. Starting with the smallest element was just an idea by me, any rotation that can easily produced will do.

That's a fine way to start, but more work than is needed.

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?

Cheers,
Cameron Simpson <cs@zip.com.au>

[toc] | [prev] | [next] | [standalone]

#94873

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web