在Python中的列表模式查找器？

Question

我想做一个python列表模式查找器。我的第一个想法是获取列表中的第一个值，然后找到下一个出现的相同值。这就是潜在的模式序列长度，然后我会检查从第一个数字到第二个数字是否等于潜在模式序列长度范围内第二个数字之后的值。你知道吗

例如：

如果我有这个清单

[1, 2, 6, 1, 2, 6, 1, 2, 6, 7, 8, 7, 8]

然后它将取第一个数字1，并取列表中第二个1的索引，然后取第一个的索引。所以3 - 0 = 3，这就是模式长度。然后它会检查list[:3] == list[3:3 + pattern length]。等等，直到图案不匹配。最终结果将是[[3, [1, 2, 6]], [2, [7, 8]]]。最好有一个dictionary作为输出，但是如果两个模式相同，dictionaru就不起作用，因为它不能有两个相同的键。你知道吗

我发现这个方法不是很有效，或者我的函数没有完全成功，所以我想知道是否有人可以帮助我使用另一个pattern finder函数的想法，或者是否有一个python模块。你知道吗

我在网上找到了：https://regex101.com/r/Vdhjld/1，这正是我想要的，但我的实际列表非常大，使用这个列表需要花费很多时间。我该怎么做有什么想法吗？你知道吗

如果描述不清楚，请评论

Answer 1

我写这篇文章是作为一个答案，因为这是一个详细的评论。
我认为你应该首先明确你的要求，这不是一个微不足道的问题，有多种解决方案，尤其是你的问题，如果它是一个长长的清单。你知道吗

可能出现的问题的一些示例：

让我们先看下面的列表：

[1, 2, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1]

有多种（所有正确的）解决方案可用于查找此列表中的模式：

1. [3, [1, 2], 1, [3], 2, [1, 2] , 1, [3, 1, 2, 1]
2. [1, [1, 2], 2, [1, 2, 1, 2, 3], 1, [1, 2, 1]]
3. [1, [1], 2, [2, 1], 2, [2, 3, 1, 2, 1]]
4. [2, [1, 2], 2, [1, 2, 3, 1, 2], 1 [1]]

以下哪一个应该是你问题的“正确”答案？即使我们说，子序列最长的那一个，我们还有三个不同的解。只有当列表长度为15，并且只有三个不同的数字时，列表越大，列表中的解决方案就越不同。我能想到的唯一解决方案是，通过搜索最长的公共序列，任意选择一个解决方案，将其从列表中删除，然后重复该操作，直到列表为空。但是，这可能会给您的排序带来问题，而且可能会非常慢。如果有人有更好的办法，我很高兴听到。你知道吗

它卡在我的脑子里，我没有别的事可做，所以我只是尝试了一下，它是未排序的，你必须这样做，但它提取最长的共同模式。不过，它是递归的，所以我不知道它是否适用于您的长列表，但它可能会给您一个如何解决它的想法。我不认为，这是迄今为止最快的方法，它只是处理它的一种方法。把它当作一个想法来使用，并在心里编写自己的代码。下面是代码（相当长）：

test = [1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 5, 4, 5, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 5, 4]
test_1 = [1, 2, 3, 1, 2, 3, 1]
test_2 = [1, 2, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2]
test_3 = [1, 1, 1, 2, 1, 1, 1]

def pattern_finder(mylist, pattern):
    matches = []
    i = 0
    while i < len(mylist):
        if mylist[i] == pattern[0] and mylist[i:i+len(pattern)] == pattern:
            matches.append(i)
            i += len(pattern)
        else:
            i+=1
    return matches

def get_patterns(list_input, p=None):
    if type(list_input[0]) != list:
        list_input = [list_input]
    result = []
    for list_in in list_input:
        if len(set(list_in)) == 1:
            result.append([1,list_in])
            continue
        n = len(list_in)
        if n == 1:
            result.append(list_in[0])
            continue
        p_len = p
        if p == None:
            p_len = int(n/2)
        lhs = 0
        rhs = lhs + p_len
        list_split = list_in
        if p_len <= 1:
            result.append([1, list_in])
            continue
        found = False
        while lhs < n - p_len and not found:
            rhs = lhs + p_len
            while rhs <= n-p_len:
                if list_in[lhs:lhs+p_len] == list_in[rhs:rhs+p_len]:
                    found = True
                    matches = pattern_finder(list_in, list_in[lhs:lhs+p_len])
                    list_split = []

                    for i,m in enumerate(matches):
                        if i == 0 and m != 0:
                            list_split.append(list_in[0:m])
                            continue
                        if i == len(matches)-1:
                            if m+p_len != n:
                                list_split.append(list_in[m+p_len:])
                            continue
                        if m+p_len != matches[i+1]:
                            list_split.append(list_in[m+p_len:matches[i+1]])
                    result.append([len(matches), list_in[lhs:lhs+p_len]])
                    break
                rhs += 1
            lhs += 1
        if list_split == []:
            continue
        if not found:
            result += get_patterns(list_split, p_len-1)
        else:
            result += get_patterns(list_split)
    return result

print("Result:", get_patterns(test))