比较python中的旋转列表

Question

我试图比较两个列表来确定一个是否是另一个的旋转(循环置换),例如:

a = [1, 2, 3]
b = [1, 2, 3] or [2, 3, 1] or [3, 1, 2]

都是比赛,而:

b = [3, 2, 1] is not

为此,我有以下代码:

def _matching_lists(a, b):
    return not [i for i, j in zip(a,b) if i != j]

def _compare_rotated_lists(a, b):
    rotations = [b[i:] + b[:i] for i in range(len(b))]
    matches = [i for i in range(len(rotations)) if _matching_lists(a, rotations[i])]
    return matches

这将构建b的所有可能旋转的列表,然后比较每个旋转.是否可以在不构建中间列表的情况下执行此操作？性能并不重要,因为列表通常只有四个项目.我主要关心的是代码的清晰度.

列表将始终具有相同的长度.

最佳答案(保持匹配轮换列表)似乎是:

def _compare_rotated_lists(a, b):
    return [i for i in range(len(b)) if a == b[i:] + b[:i]]

Answer 1

您不需要该功能_matching_lists,因为您可以使用==:

>>> [1,2,3] == [1,2,3]
True
>>> [1,2,3] == [3,1,2]
False

我建议any()尽快使用返回匹配,并使用生成器表达式来避免在内存中构建旋转列表:

def _compare_rotated_lists(a, b):
    """Return `True` if the list `a` is equal to a rotation of the list `b`."""
    return any(a == b[i:] + b[:i] for i in range(len(b)))

您可以考虑检查列表的长度是否相同,以便快速拒绝容易的情况.

    return len(a) == len(b) and any(a == b[i:] + b[:i] for i in range(len(b)))

正如在评论中讨论的,如果你知道的元素a和b是哈希的,你可以用做初步的比较collections.Counter:

    return Counter(a) == Counter(b) and any(a == b[i:] + b[:i] for i in range(len(b)))

如果您知道元素a和b可比性,您可以使用sorted以下方法进行初始比较:

    return sorted(a) == sorted(b) and any(a == b[i:] + b[:i] for i in range(len(b)))