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

Humm check this question out http://stackoverflow.com/questions/2150108/efficient-way-to-shift-a-list-in-python I think this is more or less duplicates — PyNEwbie, Apr 02 '13 at 20:33
No it's not. The other question is about how to shift a list, which I'm already doing in my code. — Stefan, Apr 02 '13 at 20:36
@Stefan yes, but you can easily use that answer to obtain a what you asked, i.e. a way to check for all rotations without building all the rotations `list`s. You simply have to convert the `list` into `deque`s and rotate one of the two lists. — Bakuriu, Apr 02 '13 at 20:37
I'd use the recommendation supplied by hcalves, because in reality you are not looking for a rotation, but a permutation. I'd suggest taking a look at both the itertools module and the sets module. With the Set class you can do things like a = Set([1,2,3]); b = Set([2,1,3]) a.issubset(b) — aquil.abdullah, Apr 02 '13 at 21:00
Edited the question to clarify rotation as a cyclic permutation, thanks @GarethRees! — Stefan, Apr 02 '13 at 21:06

Gareth Rees · Accepted Answer · 2013-04-02T20:50:22.467

8

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

edited Apr 02 '13 at 20:50

answered Apr 02 '13 at 20:33

Gareth Rees

64,967
9
133
163

It's probably worth pointing out that you're also using a [generator expression](http://www.python.org/dev/peps/pep-0289/) instead of list comprehension, since there's no need to store the list. – Brendan Long Apr 02 '13 at 20:34
1

Would it not be better to confirm first that the set a == the set b. b cannot be a rotation of a unless they have the same members, this seems like a cheap/inexpensive check before any number crunching – PyNEwbie Apr 02 '13 at 20:38
Instead(or in addition) of `len(a) == len(b)` it's better to do `sorted(a) == sorted(b)` to also check tons of other cases(the `any` expression is O(n^2) and thus the extra O(nlogn) doesn't hurt. Using `set`s also works, in O(n) amortized time, but checks less cases). – Bakuriu Apr 02 '13 at 20:39
@Bakuriu: Using `sorted` relies on the elements of `a` and `b` being comparable. @PyNEwbie: Using `set` relies on the elements of `a` and `b` being hashable. So either of these techniques would reduce the generality of the function. But yes, if you know that your elements are comparable or hashable, it would make sense. – Gareth Rees Apr 02 '13 at 20:41
All OP's examples use `int`s which are both comparable and hashable. – Bakuriu Apr 02 '13 at 20:43
Why reinvent itertools.permutations? – hcalves Apr 02 '13 at 20:46
@hcalves: the OP wants to know if the lists are *rotations* of each other, not *permutations*. – Gareth Rees Apr 02 '13 at 20:51
To answer some of the comments: yes, I want rotations, not permutations. The objects I will be comparing will be hashable, but may not be comparable. – Stefan Apr 02 '13 at 20:54
@GarethRees I had a different impression from the examples he showed, looks like he misused the word rotation (he says [2, 3, 1] or [3, 1, 2] are matches, [3,2,1] isn't). – hcalves Apr 02 '13 at 20:54
2

@hcalves: There are different senses of *rotation*, but Stefan's using it to mean [*cyclic permutation*](http://en.wikipedia.org/wiki/Cyclic_permutation). – Gareth Rees Apr 02 '13 at 20:58
1

@GarethRees Thanks, I wasn't aware of this usage of word rotation, now I see what he means. – hcalves Apr 02 '13 at 21:00

hcalves · Answer 2 · 2013-04-02T20:47:57.120

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

edited Apr 02 '13 at 20:47

answered Apr 02 '13 at 20:42

hcalves

2,268
1
21
17

score 1 · Answer 3 · answered Apr 02 '13 at 20:54

1

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.

answered Apr 02 '13 at 20:54

georg

211,518
52
313
390

This doesn't work if there can be duplicate elements in the sequence. `is_rotation('abad', 'bada') # False` – Stef May 05 '22 at 22:35

score 0 · Answer 4 · answered Apr 02 '13 at 20:42

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.

Compare rotated lists in python

4 Answers4

Linked