Python中比较旋转列表

Question

我正在尝试比较两个列表，以确定它们是否是彼此的旋转（循环置换），例如：

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

所有匹配项为“matches”，而：

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

这段代码生成了一个旋转列表，并逐一比较每个旋转。是否有可能不生成中间列表而实现同样的功能？由于这些列表通常只包含四个项目，因此性能并不重要。我的主要关注点是代码的清晰易懂。

这些列表的长度始终相同。

最佳答案（保留匹配旋转列表）似乎是：

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

- Stefan

---

嗯，看看这个问题：https://dev59.com/VnI95IYBdhLWcg3wyRM0 我认为这多少是重复的。 - PyNEwbie

不是这样的。另一个问题是关于如何移动列表，而我已经在我的代码中做了。 - Stefan

@Stefan 是的，但你可以轻松地使用那个答案来获得你所要求的东西，即一种检查所有旋转而不建立所有旋转列表的方法。你只需要将list转换为deque并旋转其中一个列表即可。 - Bakuriu

我会使用hcalves提供的建议，因为实际上你不是在寻找旋转，而是排列。我建议查看itertools模块和sets模块。使用Set类，您可以执行诸如a = Set([1,2,3]); b = Set([2,1,3]) a.issubset(b)之类的操作。 - aquil.abdullah

编辑了问题以澄清旋转为循环置换，感谢@GarethRees！ - Stefan

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)))

- Gareth Rees

---

首先确认集合a == 集合b不是更好的选择吗？除非它们具有相同的成员，否则b不能是a的旋转，这似乎是在进行任何计算之前进行的一项简单/廉价的检查。 - PyNEwbie

与其使用len(a) == len(b)，最好使用sorted(a) == sorted(b)来检查更多的情况（any表达式是O(n^2)，因此额外的O(nlogn)不会有影响）。使用set也可以，在摊销时间O(n)内完成，但检查的情况较少。 - Bakuriu

为什么要重新发明itertools.permutations？ - hcalves

@hcalves：旋转有不同的意义，但Stefan使用它来表示循环置换。（参见http://en.wikipedia.org/wiki/Cyclic_permutation） - Gareth Rees

@GarethRees 谢谢，我之前不知道“rotation”还有这种用法，现在我明白他的意思了。 - hcalves

Answer 2

如果我理解正确，您想找出b是否是a的排列，但不是a的反向？这里有一个非常简单、易读且通用的解决方案：

>>> from itertools import permutations 
>>> a = (1, 2, 3)
>>> b = (3, 1, 2)
>>> c = (3, 2, 1)
>>> results = set(permutations(a)) - set((a, tuple(sorted(a, reverse=True))))
>>> b in results
True
>>> c in results
False

- hcalves

Answer 3

怎么样：

def canon(seq):
    n = seq.index(min(seq))
    return seq[n:] + seq[:n]

def is_rotation(a, b):
    return canon(a) == canon(b)

print is_rotation('abcd', 'cdab') # True
print is_rotation('abcd', 'cdba') # False

不需要生成所有旋转来确定两个列表是否彼此旋转。

- georg

---

如果序列中存在重复元素，则此方法无法正常工作。“is_rotation('abad', 'bada') # False”。 - Stef

Answer 4

我用几个例子测试了这段代码，它运行良好。

def compare(a,b):
firstInA = a[0]
firstInB = b.index(firstInA)
secondInA = a[1]
secondInB = b.index(secondInA)
if (secondInB == firstInB + 1) or (secondInB == 0 and firstInB == 2):
    return True
else:
    return False

我尝试了：

a = [1,2,3]
b = [1,2,3]
print(compare(a,b))
c = [1,2,3]
d = [3,1,2]
print(compare(c,d))
e = [1,2,3]
f = [3,2,1]
print(compare(e,f))

他们返回了True，True，False。这仅适用于大小为3的列表。如果您想要更多，请在if语句中添加thirdInA和thirdInB，您始终需要比列表长度少一个，因为如果您知道除了一个位置外，所有位置都正确，那么最后一个位置只有一个空位。

- erdekhayser