创建或使用函数来查找列表中重复的项目序列

Question

采用列表/数组并查找重复数字序列的函数。

示例

[111, 0, 3, 1, 111, 0, 3, 1, 111, 0, 3, 1]

[111, 0, 3, 1]

是正在重复的块，也是我正在寻找的。

[11, 34, 132, 54, 90, 430, 657, 689, 34, 90, 90, 90, 46, 34, 657, 689, 34, 90, 90, 90, 46, 34, 657, 689, 34, 90, 90, 90, 46, 34]

[657, 689, 34, 90, 90, 90, 46, 34]

是重复的子列表。

[569, 374, 879, 374, 879, 460, 568, 488, 460, 568, 488, 460, 568, 488, 750, 750]

这有 2 个

[374, 879]

；

[460, 568, 488]

。

[45, 98, 45, 98, 45]

[45, 98]

是块而不是

[98, 45]

，因为它不在开始处。从一开始就识别块，并排除

[98, 45]

，因为它开始与

[45, 98]

重叠。

数据集的一些限制。

• 整个列表不是重复序列
• 重复序列至少会完整存在两次
• 可以出现在列表的任意位置（开头/中间/结尾）
• 它可能不会与自身或其他序列重叠，如果重叠，则应选择最大的一个
• 可能存在多个
• 一个区块至少有两个项目
• 较小的块可能会组成一个较大的块，因此应优先考虑最大的块

  [230, 205, 900, 617, 821, 188, 617, 821, 205, 900]

  ，

  [617, 821]

  是一个块，但不是有效的块，因为它位于内部

  [205, 900, 617, 821, 188, 617, 821, 205, 900]

预期结果

该函数应该返回一个方便的数据结构，例如列表列表、键值对或列表列表，指示从初始位置到第一个结束的每个唯一重复的开始和结束。应维持初始订购。

尝试

def get_seq_group(seq):
    return [(key, list(group)) for key, group in itertools.groupby(seq)]

list_a = [111, 0, 3, 1, 111, 0, 3, 1, 111, 0, 3, 1]
list_b = [67, 4, 67, 4, 67, 4, 67, 4, 2, 9, 0]
list_c = [11, 34, 132, 54, 90, 430, 657, 689, 34, 90, 90, 90, 46, 34, 657, 689, 34, 90, 90, 90, 46, 34, 657, 689, 34,
          90, 90, 90, 46, 34]
list_d = [569, 374, 879, 374, 879, 460, 568, 488, 460, 568, 488, 460, 568, 488, 750, 750]

print(get_seq_group(list_a))
print(get_seq_group(list_b))
print(get_seq_group(list_c))
print(get_seq_group(list_d))

我尝试将它们分组，但没有成功。它仅返回每个实例的键值对，因为相邻数字不相同。

[(111, [111]), (0, [0]), (3, [3]), (1, [1]), (111, [111]), (0, [0]), (3, [3]), (1, [1]), (111, [111]), (0, [0]), (3, [3]), (1, [1])]

输出

list_a

。

我不知道有任何算法可以解决这种情况。

我尝试将内容转换为字符串并连接它们，但返回列表是不可能的，因为所有数字都会合并。 here的解决方案对我也不起作用。

任何提供的算法的解释也很好。 函数式和命令式解决方案也将因对比而受到赞赏。

Answer 1

您可以尝试使用

re

模块（链接到Regex101）：

import re


testcases = [
    [111, 0, 3, 1, 111, 0, 3, 1, 111, 0, 3, 1],
    [11, 34, 132, 54, 90, 430, 657, 689, 34, 90, 90, 90, 46, 34, 657, 689, 34, 90, 90, 90, 46, 34, 657, 689, 34, 90, 90, 90, 46, 34],
    [569, 374, 879, 374, 879, 460, 568, 488, 460, 568, 488, 460, 568, 488, 750, 750],
    [45, 98, 45, 98, 45]
]


for t in testcases:
    s = " ".join(map(str, t)) + " "
    out = [
        [int(v) for v in r.split()] for r in re.findall(r"(\b(?:\d+\s+){2,}).*\1", s)
    ]
    print(t)
    print(out)
    print()

打印：

[111, 0, 3, 1, 111, 0, 3, 1, 111, 0, 3, 1]
[[111, 0, 3, 1]]

[11, 34, 132, 54, 90, 430, 657, 689, 34, 90, 90, 90, 46, 34, 657, 689, 34, 90, 90, 90, 46, 34, 657, 689, 34, 90, 90, 90, 46, 34]
[[657, 689, 34, 90, 90, 90, 46, 34]]

[569, 374, 879, 374, 879, 460, 568, 488, 460, 568, 488, 460, 568, 488, 750, 750]
[[374, 879], [460, 568, 488]]

[45, 98, 45, 98, 45]
[[45, 98]]