Python列表重复模式识别：网络确定性游走的瞬态与周期检测

函数参数与返回值说明 #

• 入参：A 为所有已访问节点的全量列表
• 返回值为三元组：(是否停止: bool, 瞬态段: list|None, 周期子列表: list|None)

核心思路 #

每次调用时仅检查列表末尾的连续重复段即可（因为轨迹是按步追加的，符合要求的周期必然出现在列表尾部），逻辑如下：

• 先排除长度不足的情况：列表长度小于3时不可能存在连续重复3次的周期，直接返回未检测到
• 遍历所有可能的周期长度L，取值范围为1 到 len(A)//3（连续重复3次至少需要3*L个元素）
• 对每个候选周期长度，校验列表末尾的3*L个元素是否恰好由同一个长度为L的子列表重复3次构成
• 校验通过后，找到该周期首次出现的起始位置，起始位置之前的子列表即为瞬态段

实现代码 #

def check_cycle_stop(A):
    n = len(A)
    # 列表长度不足直接返回未检测到
    if n < 3:
        return False, None, None
    # 遍历所有可能的周期长度
    max_possible_L = n // 3
    for L in range(1, max_possible_L + 1):
        # 取末尾三段长度为L的子列表做校验
        seg1 = A[-3*L : -2*L]
        seg2 = A[-2*L : -L]
        seg3 = A[-L :]
        if seg1 == seg2 == seg3:
            C = seg3
            # 定位周期首次出现的起始索引
            start_idx = 0
            for i in range(n - 3*L + 1):
                if A[i:i+L] == C:
                    start_idx = i
                    break
            # 提取瞬态段
            t = A[:start_idx]
            return True, t, C
    # 未找到符合要求的周期
    return False, None, None

调用与测试示例 #

示例场景测试 #

A = [0, 1, 4, 6, 1, 2, 1, 2, 1, 2]
is_stop, t, C = check_cycle_stop(A)
print(is_stop) # 输出 True
print(t) # 输出 [0, 1, 4, 6]
print(C) # 输出 [1, 2]

游走主逻辑调用方式 #

A = []
while True:
    new_node = trajectory() # 你的游走步执行函数
    A.append(new_node)
    is_stop, t, C = check_cycle_stop(A)
    if is_stop:
        print(f"停止游走，瞬态段：{t}，周期：{C}")
        break

内容的提问来源于stack exchange，提问作者Joao Vitor Bevilacqua de Souza