2

我正在尝试比较两个列表以确定一个是否是另一个的旋转（循环排列），例如：

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]]
4

4 回答 4

7

您不需要该功能_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)))
于 2013-04-02T20:33:56.397 回答
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
于 2013-04-02T20:42:43.413 回答
1

怎么样：

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

无需生成所有旋转来确定两个列表是否相互旋转。

于 2013-04-02T20:54:02.973 回答
0

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

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，并且您总是需要比列表的长度少一个，因为如果您知道除了一个到位，那么就只剩下最后一个了。

于 2013-04-02T20:42:34.993 回答