在列表中寻找模式

3 投票

3 回答

16517 浏览

数据工程师

提问于 2025-04-16 21:18

我正在尝试写一个Python脚本，用来在一个列表中找出重复的模式。

比如，给定这个列表：

[1,2,3,4,5,6,4,5,6,4,5,6,4,5,6]

这个脚本会判断出4,5,6出现了3次，然后打印出：

3 (4,5,6)

我希望有人能给我一些算法方面的建议（我现在只能想到n^2的算法，就是每次检查长度为1、2、3的模式，逐个遍历这个列表），或者有没有什么Python的内置库可以帮助实现这个功能。谢谢！

算法优化数据分析模式识别列表处理重复检测频率计数子序列查找

3 个回答

你要找的算法叫做游程编码。这个算法的基本原理可以帮助你识别序列中的模式并进行计数。

游程编码（RLE）是一种非常简单的数据压缩方式，它把一段连续的数据（也就是说，很多相同的数据值连续出现的部分）存储为一个数据值和它出现的次数，而不是保存原来的那一段数据。

这里有一篇相关的文章，介绍了如何用Python编写RLE程序。

回答于 2025-04-16 由 Python大师

分享举报

这里有一个函数，可以解决模式匹配的问题：

import itertools

def pattern_match(pattern, sequence):
    """Count the number of times that pattern occurs in the sequence."""
    pattern = tuple(pattern)
    k = len(pattern)

    # create k iterators for the sequence
    i = itertools.tee(sequence, k)

    # advance the iterators
    for j in range(k):
        for _ in range(j):
            next(i[j])

    count = 0
    for q in zip(*i):
        if pattern == q:
            count += 1

    return count

要解决这个问题，可以这样调用：

p = [4, 5, 6]
l = [1, 2, 3, 4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6]
count = pattern_match(p, l)

这里有一个完整的代码示例，可以帮助你理解如何解决这个例子中的问题。

（我认为正确的答案是模式重复了4次，而不是问题中提到的3次。）

我不太确定这个算法的复杂度是否真的低于O(n^2)。

回答于 2025-04-16 由 Python大师

分享举报

我想到的做法是这样的：

先准备两个列表，分别叫做 A 和 B。
从 B 中取出第一个值（也就是把它移除）。
用 A 减去 B，得到一个新的列表 C：C = A - B。
在 C 中查找值为 0 的地方；这些地方表示有重复的字符串。
把重复的字符串放进一个字典里，这个字典用来记录每个字符串和它出现的次数。
重复步骤 2 到 5，直到 B 变空为止。

回答于 2025-04-16 由 Python大师

分享举报

在列表中寻找模式

3 个回答

撰写回答