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
--
https://mail.python.org/mailman/listinfo/python-list
