Compare rotated lists in python

Question

I'm trying to compare two lists to determine if one is a rotation (cyclic permutation) of the other, e.g.:

a = [1, 2, 3]
b = [1, 2, 3] or [2, 3, 1] or [3, 1, 2]

are all matches, whereas:

b = [3, 2, 1] is not

To do this I've got the following code:

def _matching_lists(a, b):
    return not [i for i, j in zip(a,b) if i != j]

def _compare_rotated_lists(a, b):
    rotations = [b[i:] + b[:i] for i in range(len(b))]
    matches = [i for i in range(len(rotations)) if _matching_lists(a, rotations[i])]
    return matches

This builds a list of all possible rotations of b and then compares each one. Is it possible to do this without building the intermediate list? Performance isn't important since the lists will typically only be four items long. My primary concern is clarity of code.

The lists will always have the same length.

Best answer (keeping the list of matching rotations) seems to be:

def _compare_rotated_lists(a, b):
    return [i for i in range(len(b)) if a == b[i:] + b[:i]]

Answer 1

You don't need the function _matching_lists, as you can just use ==:

>>> [1,2,3] == [1,2,3]
True
>>> [1,2,3] == [3,1,2]
False

I suggest using any() to return as soon a match is found, and using a generator expression to avoid constructing a list of rotations in memory:

def _compare_rotated_lists(a, b):
    """Return `True` if the list `a` is equal to a rotation of the list `b`."""
    return any(a == b[i:] + b[:i] for i in range(len(b)))

You might consider checking that the lists are the same length, to reject the easy case quickly.

    return len(a) == len(b) and any(a == b[i:] + b[:i] for i in range(len(b)))

As discussed in comments, if you know that the elements of a and b are hashable, you can do the initial comparison using collections.Counter:

    return Counter(a) == Counter(b) and any(a == b[i:] + b[:i] for i in range(len(b)))

and if you know that the elements of a and b are comparable, you can do the initial comparison using sorted:

    return sorted(a) == sorted(b) and any(a == b[i:] + b[:i] for i in range(len(b)))

Answer 2

If I understood correctly, you want to find if b is a permutation of a, but not a reversed? There's a very simple, readable, and general solution:

>>> from itertools import permutations 
>>> a = (1, 2, 3)
>>> b = (3, 1, 2)
>>> c = (3, 2, 1)
>>> results = set(permutations(a)) - set((a, tuple(sorted(a, reverse=True))))
>>> b in results
True
>>> c in results
False

Answer 3

How about:

def canon(seq):
    n = seq.index(min(seq))
    return seq[n:] + seq[:n]

def is_rotation(a, b):
    return canon(a) == canon(b)

print is_rotation('abcd', 'cdab') # True
print is_rotation('abcd', 'cdba') # False

No need to generate all rotations just to find out if two lists are rotation of each other.

Answer 4

I tested this code with a few examples, and it worked well.

def compare(a,b):
firstInA = a[0]
firstInB = b.index(firstInA)
secondInA = a[1]
secondInB = b.index(secondInA)
if (secondInB == firstInB + 1) or (secondInB == 0 and firstInB == 2):
    return True
else:
    return False

I tried:

a = [1,2,3]
b = [1,2,3]
print(compare(a,b))
c = [1,2,3]
d = [3,1,2]
print(compare(c,d))
e = [1,2,3]
f = [3,2,1]
print(compare(e,f))

They returned True,True,False This only works with lists of size 3. If you want more, within the if statement, add a thirdInA and thirdInB, and you will always need to have one less than the length of the list, because if you know all but one is in place, then there is only on spot left for the last to be.