Determining if a list is a rotation of another list-CodePudding

I am looking for a way to detect whether two lists store identical values in the same circular order, but the starting point of that ordering may differ between the two lists.

When I talk about a circular ordering, I mean that the last element of the list can be considered as the element just before the first element of the list.

For example:

['foo', 'bar', 'baz'] == ['bar', 'baz', 'foo']
>>> True

This should output True, because 'foo' is before 'bar' which is before 'baz' in a circular way for both lists.

['foo', 'bar', 'baz'] == ['bar', 'foo', 'baz']
>>> False

This should output False, because values in list are not in same order, no matter how many times you rotate either list.

CodePudding user response：

Given the two lists, first assert that their lengths are equal. If they're not, you don't have to inspect the elements of the list -- the equality relation can't hold.

If they're the same length, create a new list that is the first list concatenated with itself. If the two lists are circularly equal, then the second list will be a sublist of the first list concatenated with itself.

So, we can do the following:

def is_circular_equal(first, second):
    if len(first) != len(second):
        return False
        
    repeated_first = first   first
    
    for start_idx in range(len(first)):
        if repeated_first[start_idx:start_idx   len(first)] == second:
            return True
    return False

CodePudding user response：

If the lists are short, then you can just make a copy of the 2nd list and rotate that so that the first word of the first list becomes the first word of the second list, then compare the two lists. Rotating a list is simple with slicing.

However, if the lists are very long, it may be too inefficient to create a new list. This simple loop avoids a copy:

def cmp_ring(lst1, lst2):
    if len(lst1) != len(lst2):
        return False
    # For each occurrence of lst1[0] in lst2...
    for start in [idx for idx,val in enumerate(lst2) if val == lst1[0]]:
        for i in range(len(lst1)):
            if lst1[i] != lst2[(i   start) % len(lst2)]:
                break
        else:
            return True
    return False

For completeness, here is the method mentioned in the first paragraph:

def cmp_ring(lst1, lst2):
    if len(lst1) != len(lst2): return False
    for start in [idx for idx,val in enumerate(lst2) if val == lst1[0]]:
        if lst1 == lst2[start:]   lst2[:start]: return True
    return False