Python中如何高效识别并收集唯一的循环模式？

要处理这种旋转等价的模式去重问题，核心思路是给每个循环等价类生成一个唯一的“规范代表”——也就是说，把所有旋转后相同的模式映射到同一个标准形式，这样只需要检查这个标准形式是否已经出现过，就能判断是不是新的模式了。

具体实现步骤 #

1. 生成模式的所有旋转变体：对于长度为8的patternList，它的旋转变体就是把前k个元素移到末尾（k从0到7）得到的8个列表。
2. 选择规范代表：从所有旋转变体中选出字典序最小的那个（或者最大的，只要统一规则就行），作为这个循环模式的唯一标识。
3. 用集合跟踪已见过的模式：集合的查找操作是O(1)，比遍历列表高效得多，用来存储已经出现过的规范代表，避免重复添加。

代码示例 #

首先实现生成规范代表的函数，这里提供两种方式：

方式一：直接生成所有旋转变体（简单直观，适合固定短长度）

import numpy as np

def get_canonical_pattern(pattern):
    pattern_tuple = tuple(pattern)
    n = len(pattern_tuple)
    # 生成所有旋转变体，转成元组（因为列表不可哈希，元组可以存在集合里）
    rotations = [pattern_tuple[k:] + pattern_tuple[:k] for k in range(n)]
    # 返回字典序最小的变体作为规范形式
    return min(rotations)

# 你的主逻辑
circ_pattern_Collection = []
seen_canonical = set()

for j in range(10000):
    array = np.random.randint(-1000, 1000, (3, 3))
    patternList = createPattern(array)
    canonical = get_canonical_pattern(patternList)
    if canonical not in seen_canonical:
        seen_canonical.add(canonical)
        # 可以选择存储规范形式，或者原patternList，这里存规范形式保证一致性
        circ_pattern_Collection.append(list(canonical))

方式二：用最小表示法（O(n)时间复杂度，适合长序列）

如果以后你的模式长度变长，直接生成所有变体效率会下降，这时可以用KMP算法衍生的最小表示法来快速找到规范代表：

def get_canonical_pattern(pattern):
    s = tuple(pattern)
    n = len(s)
    i, j, k = 0, 1, 0
    while i < n and j < n and k < n:
        a = s[(i + k) % n]
        b = s[(j + k) % n]
        if a == b:
            k += 1
        else:
            if a > b:
                i += k + 1
            else:
                j += k + 1
            if i == j:
                j += 1
            k = 0
    start = min(i, j)
    return s[start:] + s[:start]

为什么这个方案更好？ #

• 优雅简洁：不需要写大量if判断，用数学上的等价类思想解决问题，逻辑清晰易维护。
• 高效：集合的查找是O(1)，生成规范代表的操作对于长度8的序列来说几乎没有性能开销。
• 可扩展：不管模式长度是8还是其他值，只需要调整函数里的长度逻辑，不需要修改主循环。

内容的提问来源于stack exchange，提问作者JustANoob