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

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'。

- Tóth Tamás

---

请提供您所尝试的代码。 - jpllosa

我还没有任何有希望的代码 :( - Tóth Tamás

即使是伪代码也可以作为一种开始。我们在这里不是来为你编写代码，而是为了帮助你。 - aloisdg

值得注意的是，你可以用比O(n^2)更好的方法来解决这个问题。 我已经发现了一个真正非凡的证明，但这个边距太小无法容纳。 - Cireo

@Cireo。我想我也找到了一个答案。你不会在看第一个元素的频率，是吧？ - Mad Physicist

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([])
[]

- user3064538

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

- cdlane

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]'。

- Tóth Tamás

Answer 4

简单解决方案：

def get_unique_items_list(some_list):
    new_list = []
    for i in range(len(some_list)):
        if not some_list[i] in new_list:
            new_list.append(some_list[i])
    return new_list

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

print(get_unique_items_list(l1))
print(get_unique_items_list(l2))

#### Output ####
# [8, 9]
# [3, 4, 2]

- Adnan Mohib

---

谢谢，很好，但是l2的结果是错误的。因为如果你重复[3,4,2]，下一个元素是3，但在我的例子中，下一个元素是4。所以正确的答案是[3,4,2,4]。 - Tóth Tamás

你的意思是，你想检测完整的序列或序列数量，而不是仅重复的唯一值，对吗？ - Adnan Mohib

你能分享几个测试用例以使问题更清晰吗？ - Adnan Mohib

我需要最小的重复部分，只要在某处切割，你就能得到答案。例如： 19391 --> 1939（因为如果你继续使用第一个元素，你将得到原始数字， 13413413 --> 134， 11111 --> 1 - Tóth Tamás