# Compare two lists to see if one is a rotation of the other 2

Second attempt to solve this rotation problem, implemented a double ended queue as was suggested in a comment of my first attempt. So did I finally do the problem some justice or is there perhaps a better solution? Also anything I can and should clean up? I wanted to thank everyone from my previous post for their help and suggestions!

'''
Attempt 2
Problem statement: Given 2 integer arrays, determine if the 2nd array is a rotated version of the 1st array.
Ex. Original Array A={1,2,3,5,6,7,8} Rotated Array B={5,6,7,8,1,2,3}

@author: Anonymous3.1415
'''

from collections import deque

def is_rotated(lst1, lst2):
'''is lst2 a rotation of lst1 '''

if len(lst1) != len(lst2):
return False
if lst1 == [] and lst2 == []:
return True

d_lst1 = deque(lst1)
d_lst2 = deque(lst2)

#rotate all possible rotations to find match
for n in range(len(d_lst1)):
d_lst2.rotate(n)
if d_lst2 == d_lst1:
return True
d_lst2.rotate(-n)
return False

# rotation
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,7,1,2,3,4]
assert is_rotated(lst1, lst2)

# rotation with repeated numbers
lst1, lst2 = [1,2,3,4,6,4,7,1], [6,4,7,1,1,2,3,4]
assert is_rotated(lst1, lst2)

# different set
lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
assert not is_rotated(lst1, lst2)

# equal
lst2 = lst1
assert is_rotated(lst1, lst2)

# empty
lst1, lst2 = [], []
assert is_rotated(lst1, lst2)

# 1 empty, 1 not empty
lst1, lst2 = [], 
assert not is_rotated(lst1, lst2)
lst1, lst2 = , []
assert not is_rotated(lst1, lst2)


## 1 Answer

If you compare one of the lists with all the rotations of the other list, this will take $\Theta(n^2)$ in the worst case.

For example, if we make test cases like this:

from timeit import timeit
def test(n):
l1 =  * n
l2 =  * (n - 1) + 
return timeit(lambda:is_rotated(l1, l2), number=1)


then the quadratic runtime can be clearly seen in the timings:

>>> test(10**3)
0.009426131844520569
>>> test(10**4)
0.5701698779594153
>>> test(10**5)
57.70295810396783


There are a couple of ways to solve this problem in linear time:

1. Search for one list in the concatenation of the other list with itself, using a search algorithm that has linear time in the worst case, for example Knuth–Morris–Pratt.

Here's an illustration of this approach using strings instead of lists:

>>> a, b = 'basketwork', 'workbasket'
>>> a in b + b
True

2. Find the lexicographically minimal rotation of each of the lists to be compared (for example using Booth's algorithm) and see if the results are the same.

• Thank you, I want to try and utilize both ways so im going to do research and post another revision with both solutions. Question, I notice people always know of certain algorithms to help speed processes up, is there a reference that has a list of these algorithms so I can learn them myself? Or is this knowledge gained over experience from several different problems? In a sense is there a place I can go that lists many types of algorithms so I can search and learn about them and improve on my knowledge? – Anonymous3.1415 Mar 28 '18 at 22:09
• Read a book or two on algorithms, and do the exercises. When I was at university (long ago) the textbook was Aho, Hopcroft & Ullman, but Dasgupta, Papadimitriou & Vazirani is good and more up to date. There are so many algorithms that no book can list them all, but familiarity with the basics goes a long way. – Gareth Rees Mar 28 '18 at 22:56
• Awsome, im going to have to pick up a copy then, I appreciate it ive always been fasinated by this stuff – Anonymous3.1415 Mar 28 '18 at 22:58