查找列表中最小的重复片段

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()一旦找到 a 就停止False），您可以尝试使用2. 所以现在您要检查偶数索引处的每个元素是否等于第一个元素 ( 4 % 2is 0)，以及每个奇数索引是否等于第二个元素( 5 % 2is 1)。如果你一直通过这个，模式是前两个元素，所以 return 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([])[]

Answer 2

下面的代码是的返工您的方案，解决了一些问题：您发布的解决方案无法处理您自己的'abcabcab'示例。您的解决方案即使在找到有效结果后也会继续处理，然后过滤有效和无效结果。相反，一旦找到有效结果，我们就会处理并返回它。其他有效结果和无效结果将被简单地忽略。@Boris 关于在没有重复模式的情况下返回输入的问题。代码def repeated_piece(target):&nbsp; &nbsp; target = list(target)&nbsp; &nbsp; length = len(target)&nbsp; &nbsp; for final in range(1, length):&nbsp; &nbsp; &nbsp; &nbsp; result = []&nbsp; &nbsp; &nbsp; &nbsp; while len(result) < length:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for i in target[:final]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.append(i)&nbsp; &nbsp; &nbsp; &nbsp; if result[:length] == target:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return result[:final]&nbsp; &nbsp; return targetl1 = [8, 9, 8, 9, 8, 9, 8]l2 = [3, 4, 2, 4, 3]l3 = 'abcabcab'l4 = [1, 2, 3]print(*repeated_piece(l1), sep='')print(*repeated_piece(l2), sep='')print(*repeated_piece(l3), sep='')print(*repeated_piece(l4), sep='')输出% python3 test.py893424abc123%您仍然可以使用：print(''.join(map(str, repeated_piece(l1))))如果您对更简单的 Python 3 习惯用法感到不舒服：print(*repeated_piece(l1), sep='')

Answer 3

解决方案target = [8,9,8,9,8,9,8]length = len(target)result = []results = [] * lengthfor j in range(1, length):&nbsp; &nbsp; result = []&nbsp; &nbsp; while len(result) < length:&nbsp; &nbsp; &nbsp; &nbsp; for i in target[:j]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.append(i)&nbsp; &nbsp; results.append(result)final = []for i in range(0, len(results)):&nbsp; &nbsp; if results[i][:length] == target:&nbsp; &nbsp; &nbsp; &nbsp; final.append(1)&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; final.append(0)if 1 in final:&nbsp; &nbsp; solution = results[final.index(1)][:final.index(1)+1]else:&nbsp; &nbsp; solution = targetint(''.join(map(str, solution)))'结果：[8, 9]'。