Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Sun, 2 Aug 2015 13:19:16 -0500
From: Tim Chase <python.list@tim.thechases.com>
To: python-list@python.org
Subject: Re: Most pythonic way of rotating a circular list to a canonical point
In-Reply-To: <e71d031f-f1cf-4e16-9b5a-963d02373fb5@googlegroups.com>
References: <e71d031f-f1cf-4e16-9b5a-963d02373fb5@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.1158.1438544186.3674.python-list@python.org>
Lines: 69
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python: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