深度嵌套列表逐元素复制修改与有向图顶点生成技术问询

一、核心问题梳理 #

你需要解决三个核心问题：

• 深度嵌套列表的深复制+定点修改：完整复制父顶点结构，仅修改指定位置的元素/子列表
• 对称等价顶点去重：利用递归排序后的标准化列表作为唯一标识，避免重复顶点
• 转移边的生成：从父顶点出发，为所有合法修改生成的子顶点（或其等价顶点）建立有向边

二、分步实现方案 #

1. 嵌套列表的深复制与定点修改 #

递归实现深复制，通过索引元组指定修改路径（比如(0,1)表示深度2列表中第一个子列表的第二个元素），到达目标路径时替换为指定值（0或全0子结构）：

def deep_copy_modify(original, path, new_val):
    # 递归复制并修改指定路径的元素/子结构
    if not path:
        # 到达目标节点，返回新值（子结构需递归生成全0）
        if isinstance(new_val, list):
            return [deep_copy_modify(sub, (), 0) for sub in new_val]
        return new_val
    # 逐层复制并处理目标路径
    copied = []
    for idx, item in enumerate(original):
        if idx == path[0]:
            copied.append(deep_copy_modify(item, path[1:], new_val))
        else:
            # 递归复制非目标路径的元素
            copied.append(deep_copy_modify(item, (), item))
    return copied

# 生成与输入结构一致的全0嵌套列表（复用你已实现的逻辑）
def generate_zero_structure(original):
    if not isinstance(original, list):
        return 0
    return [generate_zero_structure(sub) for sub in original]

2. 对称等价顶点的映射与去重 #

维护一个字典，以递归排序后的标准化列表（你的判断函数输出）为键，存储对应的顶点实例。每次生成新顶点时先标准化，避免重复创建：

# 递归排序生成标准化列表（你已实现的等价判断核心）
def recursive_sort(lst):
    if not isinstance(lst, list):
        return lst
    return sorted(recursive_sort(sub) for sub in lst)

# 顶点映射表：标准化列表 -> 顶点对象
vertex_map = {}

def get_or_create_vertex(lst):
    normalized = recursive_sort(lst)
    # 列表不可哈希，转成元组作为字典键
    normalized_key = tuple(tuple(sub) if isinstance(sub, list) else sub for sub in normalized)
    if normalized_key in vertex_map:
        return vertex_map[normalized_key]
    # 顶点对象存储原始列表与标准化标识
    vertex = {"original": lst, "normalized": normalized_key, "edges": []}
    vertex_map[normalized_key] = vertex
    return vertex

3. 按层级生成所有顶点与转移边 #

按照你预期的流程，从初始顶点出发，逐层处理不同深度的可修改位置，生成子顶点并建立边：

def generate_transitions(vertex, current_depth):
    original_lst = vertex["original"]
    # 处理当前深度的可修改项
    if current_depth == 1:
        # 最深层：逐个修改叶子节点为0
        for idx in range(len(original_lst)):
            if original_lst[idx] == 1:
                modified_lst = deep_copy_modify(original_lst, (idx,), 0)
                child_vertex = get_or_create_vertex(modified_lst)
                if child_vertex not in vertex["edges"]:
                    vertex["edges"].append(child_vertex)
    else:
        # 非最深层：先修改整个子结构为全0
        for idx in range(len(original_lst)):
            zero_sub = generate_zero_structure(original_lst[idx])
            modified_lst = deep_copy_modify(original_lst, (idx,), zero_sub)
            child_vertex = get_or_create_vertex(modified_lst)
            if child_vertex not in vertex["edges"]:
                vertex["edges"].append(child_vertex)
        # 递归处理子结构的更深层级修改
        for idx in range(len(original_lst)):
            sub_vertex = get_or_create_vertex(original_lst[idx])
            generate_transitions(sub_vertex, current_depth - 1)
            # 将子结构的修改映射到当前顶点的修改
            for sub_child in sub_vertex["edges"]:
                modified_lst = deep_copy_modify(original_lst, (idx,), sub_child["original"])
                child_vertex = get_or_create_vertex(modified_lst)
                if child_vertex not in vertex["edges"]:
                    vertex["edges"].append(child_vertex)

# 初始化执行（以深度2的初始列表为例）
initial_lst = [[1,1],[1,1]]
initial_vertex = get_or_create_vertex(initial_lst)
generate_transitions(initial_vertex, depth=2)

三、优化提示 #

• 哈希效率优化：将标准化后的嵌套列表转为嵌套元组作为字典键，比列表更适合哈希存储
• 边去重：添加边时检查是否已存在，避免重复边
• 替代方案：如果已通过itertools.combinations_with_replacement生成所有唯一顶点，可遍历顶点对，判断是否存在“一步修改”关系（仅一个位置元素/子结构不同），直接建立边

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