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

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

下面的代码是的返工您的方案，解决了一些问题：

1. 您发布的解决方案无法处理您自己的'abcabcab'示例。

2. 您的解决方案即使在找到有效结果后也会继续处理，然后过滤有效和无效结果。相反，一旦找到有效结果，我们就会处理并返回它。其他有效结果和无效结果将被简单地忽略。

3. @Boris 关于在没有重复模式的情况下返回输入的问题。

代码

def repeated_piece(target):

    target = list(target)

    length = len(target)

    for final in range(1, length):

        result = []

        while len(result) < length:

            for i in target[:final]:

                result.append(i)

        if result[:length] == target:

            return result[:final]

    return target

l1 = [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.py

89

3424

abc

123

%

您仍然可以使用：

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 = [] * length

for j in range(1, length):

    result = []

    while len(result) < length:

        for i in target[:j]:

            result.append(i)

    results.append(result)

final = []

for i in range(0, len(results)):

    if results[i][:length] == target:

        final.append(1)

    else:

        final.append(0)

if 1 in final:

    solution = results[final.index(1)][:final.index(1)+1]

else:

    solution = target

int(''.join(map(str, solution)))

'结果：[8, 9]'。