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]]
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)))