python - 查找列表中最小的重复部分

Question

我有一些整数列表，例如:

l1 = [8,9,8,9,8,9,8], 
l2 = [3,4,2,4,3]

我的目的是将其切成最小的重复片段。所以:

output_l1 = [8,9]
output_l2 = [3,4,2,4]

最大的问题是序列每次都没有完全完成。所以不是

'abcabcabc'

只是

'abcabcab'.

Answer 1

def shortest_repeating_sequence(inp):
    for i in range(1, len(inp)):
        if all(inp[j] == inp[j % i] for j in range(i, len(inp))):
            return inp[:i]

    # inp doesn't have a repeating pattern if we got this far
    return inp[:]

此代码为 O(n^2) .最坏的情况是一个元素重复了很多次，然后在最后破坏了模式，例如 [1, 1, 1, 1, 1, 1, 1, 1, 1, 8].

您从 1 开始，然后遍历整个列表，检查每个 inp[i] 是否等于 inp[i % 1]。任何数字 %1 都等于 0，因此您要检查输入中的每一项是否等于输入中的第一项。如果所有项都等于第一个元素，则重复模式是一个仅包含第一个元素的列表，因此我们返回 inp[:1]。

如果在某个时候你遇到了一个不等于第一个元素的元素(all() 在发现 False 时立即停止)，你尝试与 2。所以现在您要检查偶数索引处的每个元素是否等于第一个元素(4 % 2 是 0)以及每个奇数索引是否等于第二个元素项(5 % 2 是 1)。如果你一直通过这个，模式是前两个元素，所以返回 inp[:2]，否则用 3 再试一次，依此类推。

您可以执行 range(1, len(inp)+1) 然后 for 循环将处理 inp 不执行的情况'包含重复模式，但最后您必须不必要地遍历整个 inp。而且你仍然必须在最后有 return [] 来处理 inp 是空列表。

我返回列表的副本 (inp[:]) 而不是列表以具有一致的行为。如果我使用 return inp 返回原始列表，并且有人在没有重复模式的列表上调用了该函数(即他们的重复模式是原始列表)，然后用重复模式做了一些事情, 它也会修改他们的原始列表。

shortest_repeating_sequence([4, 2, 7, 4, 6])  # no pattern
[4, 2, 7, 4, 6]
shortest_repeating_sequence([2, 3, 1, 2, 3])  # pattern doesn't repeat fully
[2, 3, 1]
shortest_repeating_sequence([2, 3, 1, 2])     # pattern doesn't repeat fully
[2, 3, 1]
shortest_repeating_sequence([8, 9, 8, 9, 8, 9, 8])
[8, 9]
shortest_repeating_sequence([1, 1, 1, 1, 1])
[1]
shortest_repeating_sequence([])
[]