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 2 of 2 — ← Prev page 1 [2]

#94882

On 01Aug2015 15:55, Lukas Barth <mail@tinloaf.de> wrote:
>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..

Are you collating on the hash before doing anything? I think I may have missed 
part of your problem specification. I thought you had a list and needed to 
recognise other lists which were rotations of it, and possibly return them pre 
or post rotation.

If you're hashing the first list I'm presuming you're using that to allocate it 
to a bucket (even notionally) to avoid wasting time comparing it against wildly 
different lists, just compare against likely matches? Or what?

If that is the case, choose a hash function that: is affected by the list 
length and is independent of the list item ordering. That is easy to arrange 
and is guarrenteed that a rotated version of the list will have the same hash.

Trivial hash function: sum(list1)+len(list1)

It is simple and will work. It has downsides that might be a problem in other 
contexts, but since I don't know what you're using the hash for then I can 
address that.

Remember, hash functions are arbitrary - they just have to obey particular 
constraints dictated by your needs.

Comments?

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

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

#94880

Am Samstag, 1. August 2015 22:34:44 UTC+2 schrieb Lukas Barth:
> 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?

It's not that much code (unless I misunderstood your question):

def f(A):
    i = min(range(len(A)-1), key=lambda i: A[i:i+2])
    if [A[-1], A[0]] < A[i:i+2]:
        i = len(A) - 1
    return A[i:] + A[:i]

Examples:

f([0,2,0,1,0,3,0])
Out[23]: [0, 0, 2, 0, 1, 0, 3]

f([2,3,4,0,1])
Out[24]: [0, 1, 2, 3, 4]


Wolfram

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

#94896

On Saturday, August 1, 2015 at 1:34:44 PM UTC-7, 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?
> 
> Thanks for enlightening me!

[[[Warning: all code untested, sorry!]]]

The general problem (no assumptions about the items in the list except that they're all sortable together) is interesting.  It doesn't seem like a simple one to me at all.  An acceptable criterion would be if you took the lexically smallest value of every rotation of the list; that would yield the same result for every initial rotation.  You can do it in like this:

    anchor = min(range(len(X)),key=lambda i:X[i:]+X[:i])
    canonical_X = X[anchor:]+X[:anchor]

I doubt this would be that efficient, though, since it happens to construct every single rotation in the process of scanning.  However, you'll notice that the minimum lexical value can only occur when the starting point is the minimum value in the list, so you can almost certainly improve performace to find all the minimum values and only test those rotations, especially if the number of minima is small compared to the list size.  (However, be sure to timeit for actual evidence rather than my guessing.)

    min_value = min(X)
    i = X.index(min_value)
    while True:
        start_points.append(i)
        try:
            i = X.index(min_value,i+1)
        except ValueError:
            break
    anchor = min(start_points,key=lambda i:X[i:]+X[:i])
    canonical_X = X[anchor:]+X[:anchor]



Your lists aren't arbitrary, however and they actually seem to be ordered pairs (in which case the first question I have is why not have it be a list of 2-tuples? but I can imagine a few reasons).  You say the pairs are known to be unique, so all you have to do is find the index of the minimum pair.  One can use zip and slicing to generate 2-tuples from the flat list, whence you can find the minimum.

    pairs = list(zip(X[0::2],X[1::2]))
    min_pair = min(pairs)
    anchor = 2 * pairs.index(min_pair)
    canonical_X = X[anchor:]+X[:anchor]


Carl Banks

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

#94900

On 2015-08-01 13:34, Lukas Barth wrote:
> 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.

Well, you can pull the minimum (or maximum) of all the rotations to
get the "canonical" version:

  def canonical(lst):
    """return the "canonical" representation of a list"""
    return min(
      lst if i == 0 else (lst[i:] + lst[:i])
      for i in range(len(lst))
      )

which you can determine, then hash once, and store.  It's not a cheap
operation, but once you've determined the canonical/hash version,
then equality-testing becomes an O(1) test if comparing hashes, or
O(N) if comparing lists rather than an O(N*2) brute-force test
(which could be lower depending on the commonality).

  def circular_compare1(a, b):
    if a == b: return True
    return any(a == (b[i:] + b[:i]) for i in range(1, len(b)))

  def circular_compare2(a, b):
    lena = len(a)
    if lena != len(b): return False
    return any(
      all(a[i] == b[(i + offset) % lena] for i in range(lena))
      for offset in range(lena)
      )

  for fn in (circular_compare1, circular_compare2):
    for (a, b), expected in (
        (([1,2,3], [1,2,3]), True), # the same
        (([1,2,3], [3,1,2]), True), # simple rotation
        (([1,2,3], [1,2,3,4]), False), # mismatched lengths
        (([0,1,0,2,0,3], [0,2,0,3,0,1]), True), # repeated elements, simple rotation
        ):
      result = bool(fn(a, b))
      if result == expected:
        print "PASS %s %r/%r=%s, not %s" % (
          fn.__name__, a, b, result, expected
          )
      else:
        print "FAIL %s %r/%r=%s, not %s" % (
          fn.__name__, a, b, result, expected
          )
      ca = canonical(a)
      cb = canonical(b)
      print "   Canonical A:", ca
      print "   Canonical B:", cb
      print "   Equal:", (ca == cb)

-tim

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

#94901

On 08/01/2015 01: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?
>
> Thanks for enlightening me!
>
> Lukas
>

Let me try to re-state what I see is your actual problem.  (Of course I could be wrong...)   ;-)

Most of the answers you have been getting concentrate on comparisons and hashes, but those are 
irrelevant to your need -- they come later.  What you are trying to do is to uniquely and 
independently determine the "starting point" for the rotation.  That is, which element will be 
rotated to index 0.  Using the minimum is possible, but that fails if that minimum appears more 
than once in the list -- it does not give a unique solution.

For a specific example...  if you are given any _one_ of these lists:
     [1, 5, 0, 3, 0], [5, 0, 3, 0, 1], [0, 3, 0, 1, 5], [3, 0, 1, 5, 0], [0, 1, 5, 0, 3]
it can be _independently_ rotated to (for example) [3, 0, 1, 5, 0]

That example does not use the minimum as the starting point, but how the starting point can be 
absolutely and uniquely determined is your fundamental problem.  I do not have an answer for 
that.  But I thought this might be a clearer description of what I think you are really looking for.

I hope I'm right.   ;-)   Good luck.

      -=- Larry -=-

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

#94928

I have this feeling that you would get a lot more useful anwsers if
you were to describe your actual problem in stead of what you think
the solution is. There might be other, better solutions but since we
know so little about what you are doing we will likely never find them
by just guessing..

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

#94953

On 08/02/2015 01:58 PM, Joonas Liik wrote:
> I have this feeling that you would get a lot more useful anwsers if
> you were to describe your actual problem in stead of what you think
> the solution is. There might be other, better solutions but since we
> know so little about what you are doing we will likely never find them
> by just guessing..
>
Sorry if I wasn't clear.  This is not _my_ problem, this was intended to re-state the OP's 
fundamental problem.  And the quoted text was the OP's original message.  I felt that most 
(anyway many) responders here were missing this point.

This is what I saw as the OP's underlying problem, but as I also said in my message, my 
interpretation certainly could be wrong.    :-)

      -=- Larry -=-

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

#94940

On 02/08/2015 21:58, Joonas Liik wrote:
> I have this feeling that you would get a lot more useful anwsers if
> you were to describe your actual problem in stead of what you think
> the solution is. There might be other, better solutions but since we
> know so little about what you are doing we will likely never find them
> by just guessing..
>

+1

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web