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 = [], [1]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1], []
assert not is_rotated(lst1, lst2)
up vote 2 down vote accepted

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 = [0] * n
    l2 = [0] * (n - 1) + [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 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 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 at 22:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.