Python嵌套序列结构一致性检测的递归算法及工具问询

需求：实现Python算法，检测两个嵌套序列（仅关注list、tuple、set，字符串视为不可拆分的简单元素，忽略字典）的结构是否一致，示例如下：

1. [0, [0, 0]]与["", ["", ""]]结构完全相同；
2. [0, [0, 0]]与[["", ""], ""]结构相同但顺序反转；
3. [0, 0, [0]]与["", "", ["", ""]]或["", [""]]深度相同但长度不同；
4. [[[0]]]与[[""]]深度不同。

问题：

1. 该问题能否通过递归解决？
2. 是否有现成的Python模块/框架可实现此功能？
3. 能否生成包含或不包含节点长度的结构树？

附未完成递归代码：

def recursion(obj):
    if type(obj) in ["<class 'list'>", "<class 'tuple'>", "<class 'set'>"]:
        for i in obj:
            recursion(i)
    else:
        pass
        # WHAT SHOULD I WRITE HERE?
    return # WHAT SHOULD IT RETURN? 

问题解答 #

1. 完全可以用递归解决 #

递归是处理嵌套结构的天然方案——每个嵌套序列的结构可拆解为「容器类型 + 子元素结构集合」，通过递归遍历每一层元素，提取结构特征即可完成检测。

2. 无专门现成模块，可自行实现核心逻辑 #

Python标准库中没有直接匹配该需求的模块，但基于递归可以快速实现核心功能，重点是提取每个节点的容器类型标记、子节点结构，按需附加节点长度信息。

3. 可以生成带/不带节点长度的结构树 #

通过递归遍历元素，将容器类型与子结构组合成树状结构，只需在递归过程中选择是否保留节点的长度参数即可实现两种模式。

实现代码 #

生成结构树（不带节点长度） #

def get_structure(obj):
    container_types = (list, tuple, set)
    if isinstance(obj, container_types):
        # set本身无序，排序子结构以统一比较标准；list/tuple保留原顺序
        sub_structures = [get_structure(item) for item in obj]
        if isinstance(obj, set):
            return (type(obj).__name__, sorted(sub_structures))
        else:
            return (type(obj).__name__, sub_structures)
    else:
        # 非容器元素统一标记为"leaf"
        return "leaf"

生成结构树（带节点长度） #

def get_structure_with_length(obj):
    container_types = (list, tuple, set)
    if isinstance(obj, container_types):
        sub_structures = [get_structure_with_length(item) for item in obj]
        if isinstance(obj, set):
            sub_structures = sorted(sub_structures)
        # 额外添加节点长度信息
        return (type(obj).__name__, len(obj), sub_structures)
    else:
        return "leaf"

结构比较函数 #

可根据需求实现多维度结构对比：

def compare_structure(a, b):
    # 先获取基础结构
    struct_a = get_structure(a)
    struct_b = get_structure(b)

    # 完全相同（类型、顺序、子结构均一致）
    if struct_a == struct_b:
        return "完全相同"
    
    # 结构相同但顺序不同（仅针对list/tuple，set本身无序）
    def normalize_struct(struct):
        if isinstance(struct, tuple) and struct[0] in ["list", "tuple"]:
            return (struct[0], sorted(struct[1]))
        return struct
    if normalize_struct(struct_a) == normalize_struct(struct_b):
        return "结构相同但顺序反转/不同"
    
    # 比较深度是否一致
    def get_depth(struct):
        if struct == "leaf":
            return 0
        max_sub_depth = max(get_depth(sub) for sub in struct[1])
        return 1 + max_sub_depth
    depth_a = get_depth(struct_a)
    depth_b = get_depth(struct_b)
    if depth_a == depth_b:
        return "深度相同但长度不同"
    else:
        return f"深度不同（{depth_a} vs {depth_b}）"

测试示例 #

# 示例1
a1 = [0, [0, 0]]
b1 = ["", ["", ""]]
print(compare_structure(a1, b1))  # 输出：完全相同

# 示例2
a2 = [0, [0, 0]]
b2 = [["", ""], ""]
print(compare_structure(a2, b2))  # 输出：结构相同但顺序反转/不同

# 示例3
a3 = [0, 0, [0]]
b3 = ["", "", ["", ""]]
print(compare_structure(a3, b3))  # 输出：深度相同但长度不同
b3_2 = ["", [""]]
print(compare_structure(a3, b3_2))  # 输出：深度相同但长度不同

# 示例4
a4 = [[[0]]]
b4 = [[""]]
print(compare_structure(a4, b4))  # 输出：深度不同（3 vs 2）

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