确定一个列表是否是另一个列表的轮换

Question

我正在寻找一种方法来检测两个列表是否以相同的循环顺序存储相同的值，但该顺序的起点在两个列表之间可能不同。

当我谈到循环排序时，我的意思是列表的最后一个元素可以被认为是列表第一个元素之前的元素。

例如：

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

这应该输出 True，因为 'foo' 在 'bar' 之前，'bar' 以循环方式在 'baz' 之前。

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

这应该输出 False，因为列表中的值顺序不同，无论您旋转哪个列表多少次。

Answer 1

给定两个列表，首先断言它们的长度相等。如果不是，则您不必检查列表的元素——等式关系不成立。

如果它们的长度相同，则创建一个新列表，该列表是第一个与其自身连接的列表。如果两个列表循环相等，则第二个列表将是第一个列表的子列表与自身连接。

因此，我们可以执行以下操作：

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

Answer 2

如果列表很短，那么你可以只复制第二个列表并旋转它，使第一个列表的第一个单词成为第二个列表的第一个单词，然后比较两个列表。通过切片旋转列表很简单。

但是，如果列表很长，创建新列表的效率可能会太低。这个简单的循环避免了复制：

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

为了完整起见，这里是第一段中提到的方法：

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

确定一个列表是否是另一个列表的轮换

Determining if a list is a rotation of another list

python

compare

list