Determine if two arrays are a rotated version of each other

Question

Similar question has been asked in JAVA, but can someone help me in improving the code: And explain what would be the time complexity and space complexity of my code. My code checks if two arrays are rotated version of each other:

list1 = [1, 2, 3, 4, 5, 6, 7]

list2b = [4, 5, 6, 7, 1, 2, 3]

is_rotation(list1, list2b) should return True.

list2c = [4, 5, 6, 9, 1, 2, 3]

is_rotation(list1, list2c) should return False.

My code:

def is_rotation (list1,list2):

    i = 0
    j = 0
    k = 0

    result = True

    if len(list1) != len(list2):
        return False  

    while i < len(list1) -1 and j < len(list1) -1:

        if list1[i] == list2[j]:
            i = i +1
            j = j +1
            break
        elif list1[i] > list2[j]:
            j = j +1
        else:
            i = i +1
    else:
        return False

    for l in range(i,len(list1)):

        if i == j:
            if list1[i] != list2[j]: 
                return False
        elif list1[i] != list2[j] or list2[i] != list1[k]:
            return False
        else:
            i = i +1
            j = j +1
            k = k +1

    return result

Answer 1

A bit hacky way:

def is_rotation(lst1, lst2):
    if(len(lst1)==len(lst2)):
        return (str(lst1)[1:-1] in str(lst2+lst2)) & (str(lst2)[1:-1] in str(lst1+lst1)) 
    else:
        return False

How does it work:

(1) check if both lists are of the same length, if not return False

(2) if they do, convert first list to string, drop the most outer brackets (by dropping first and last character- you can do any brackets there, not only square ones, it can be a tuple too).

(3) lst2+lst2 will return all the elements of lst2 duplicated in sequence (so one lst2 after another). Then converted to string it will just return its string format of list

(4) as per the comments- in order to handle the corner cases - we should check both ways, since if lst1 is rotated version of lst2 then lst2 is the rotated version of lst1

Tests

print(is_rotation([561, 1, 1, 1, 135], [1, 1, 1, 1, 1]))
#outputs False
print(is_rotation([[1,2,3,4], 2, 3, 4], [1, 2,3,4]))
#outputs False
print(is_rotation([1, 2, 3, 4, 5], [4, 5, 1, 2, 3]))
#outputs True

Answer 2

I though in another way to do this:

def is_rotation (list1,list2):
    if len(list1) != len(list2):
        return False

    for i in range(len(list1)):
        if list1[i:] + list1[:i] == list2:
            return True

    return False

1) Test if both have same length.

2) The loop will just rotate the list all the possibilities and check if in one of them both are equal..

I don't know if this is the best way, but is simple to understand ;)

Answer 3

For a somewhat more explicit approach, you can generate all the rotations of a given list using itertools, one by one, with this:

import itertools as it
def get_rotations(lst1):
    foo = it.cycle(lst1)
    for y in range(len(lst1)):
        result = []
        for x in range(len(lst1)):
            result.append(next(foo))
        yield result
        next foo

Then you can do:

def is_rotated(L1, L2) -> bool:
    bar = get_rotations(L1)
    While True:
        try:
            if next(bar) == L2;
                return True
        except StopIteration:
                return False

Aside: I think this breaks all the traditional views on using exceptions to control the normal flow of program logic, however... It feels wrong, somehow (background in C++, where we were repeatedly told to never do this kind of thing.). Is it Pythonic?

Answer 4

You can use cycle from itertools to optimize the number of comparisons and avoid creating additional copies of the data. (i.e. O(1) space in O(n) time)

Here's an example of a function that will return the rotation offset if the two lists are a rotation of each other or None if they do not match. The logic will never need more than 2N comparisons to determine the offset.

from itertools import cycle
def getRotation(listA,listB):
    if len(listA) != len(listB): return None
    unmatched,offset = len(listA),0
    iterA,iterB      = cycle(listA),cycle(listB)
    a = next(iterA)
    while unmatched and offset<len(listA):
        b = next(iterB)
        if a==b:
            unmatched -= 1
            a = next(iterA)
        else:
            unmatched = len(listA)
            offset   += 1
    if unmatched: return None
    return offset

outpu:

list1 = [1, 2, 3, 4, 5, 6, 7]
list2b = [4, 5, 6, 7, 1, 2, 3]
print(getRotation(list1,list2b)) # 4 (rotation to the right)

You can adapt it to simply return True or False if needed.

It can also be easily adapted to check if a list can be produced by cycling over the other. (e.g. [2,3,1,2,3,1,2,3,1,2] can be produced by cycling [1,2,3]). I did not include that feature in the example to avoid confusing the issue.