如何按指定匹配规则从嵌套列表构建元素链？

需求回顾 #

你提供了这样一个嵌套列表作为输入：

[['屑邪屑邪', '屑褘褌褜', '10', '褉邪屑邪'], ['屑褘褌褜', '褉邪屑邪', '5', '写芯谢谐芯'], ['屑邪屑邪', '屑褘褌褜', '10', '褉邪屑邪'], ['屑褘褌褜', '褉邪屑邪', '3', '胁褔械褉邪'], ['屑褘褌褜', '褉邪屑邪', '10', '胁褔械褉邪'], ['褉邪屑邪', '胁褔械褉邪', '1', '锌芯蟹写薪芯']]

需要按照规则构建元素链：当一个子列表的最后两个非数字字符串元素与另一个子列表的前两个非数字字符串元素匹配时，将二者拼接（数字概率值保留原样），最终得到类似这样的输出：

[['屑邪屑邪', '屑褘褌褜', '10', '褉邪屑邪', '5', '写芯谢谐芯'], ['屑邪屑邪', '屑褘褌褜', '10', '褉邪屑邪', '3', '胁褔械褉邪'], ['屑邪屑邪', '屑褘褌褜', '10', '褉邪屑邪', '3', '胁褔械褉邪', '1', '锌芯蟹写薪芯']]

实现思路 #

核心思路是先建立快速匹配的索引，再用递归延伸链：

• 第一步：为每个子列表提取「起始匹配键」（前两个非数字元素）和「结束匹配键」（最后两个非数字元素），用字典把所有子列表按起始键分组，这样可以快速找到能拼接的后续子列表。
• 第二步：从所有“无前置链”的子列表（也就是没有其他子列表能拼接到它们前面的）出发，递归地查找并拼接所有能匹配的后续子列表，直到无法继续拼接为止，最后收集所有完整的链。

Python代码实现 #

def build_element_chains(original_list):
    # 提取子列表中的非数字元素
    def get_non_num_elements(sublist):
        return [item for item in sublist if not item.isdigit()]
    
    # 构建起始键到子列表的映射，方便快速查找可拼接的后续链
    start_key_map = {}
    for sub in original_list:
        non_num = get_non_num_elements(sub)
        if len(non_num) >= 2:
            start_key = tuple(non_num[:2])
            if start_key not in start_key_map:
                start_key_map[start_key] = []
            start_key_map[start_key].append(sub)
    
    result_chains = []
    
    # 递归延伸当前链
    def extend_chain(current_chain):
        current_non_num = get_non_num_elements(current_chain)
        if len(current_non_num) < 2:
            if current_chain not in result_chains:
                result_chains.append(current_chain.copy())
            return
        
        # 获取当前链的结束匹配键
        end_key = tuple(current_non_num[-2:])
        # 查找是否有可拼接的后续子列表
        if end_key in start_key_map:
            for next_sub in start_key_map[end_key]:
                # 拼接：跳过后续子列表的前两个重复元素，只取数字和最后一个非数字元素
                extended_chain = current_chain + next_sub[2:]
                extend_chain(extended_chain)
        else:
            # 无法继续拼接，加入结果集
            if current_chain not in result_chains:
                result_chains.append(current_chain.copy())
    
    # 筛选出所有无前置链的初始子列表，作为链的起点
    for initial_sub in original_list:
        initial_non_num = get_non_num_elements(initial_sub)
        if len(initial_non_num) >= 2:
            initial_start_key = tuple(initial_non_num[:2])
            # 检查是否存在能拼接到当前子列表前面的子列表
            has_predecessor = False
            for sub in original_list:
                sub_non_num = get_non_num_elements(sub)
                if len(sub_non_num) >= 2 and tuple(sub_non_num[-2:]) == initial_start_key:
                    has_predecessor = True
                    break
            if not has_predecessor:
                extend_chain(initial_sub.copy())
    
    return result_chains

# 测试输入
original_input = [['屑邪屑邪', '屑褘褌褜', '10', '褉邪屑邪'], ['屑褘褌褜', '褉邪屑邪', '5', '写芯谢谐芯'], ['屑邪屑邪', '屑褘褌褜', '10', '褉邪屑邪'], ['屑褘褌褜', '褉邪屑邪', '3', '胁褔械褉邪'], ['屑褘褌褜', '褉邪屑邪', '10', '胁褔械褉邪'], ['褉邪屑邪', '胁褔械褉邪', '1', '锌芯蟹写薪芯']]

# 生成并打印结果
final_chains = build_element_chains(original_input)
print(final_chains)

代码说明 #

• get_non_num_elements：专门用来提取子列表中的非数字元素，帮我们快速生成匹配键。
• start_key_map：把所有子列表按起始匹配键分组，避免每次都遍历整个列表查找可拼接项，提升效率。
• extend_chain递归函数：负责不断延伸当前链，只要找到能匹配的后续子列表就拼接，直到无法延伸为止，再把完整链加入结果。
• 初始链筛选：确保我们只从最开头的链开始构建，避免生成中间链（比如单独的['屑褘褌褜', '褉邪屑邪', '5', '写芯谢谐芯']不会出现在结果里，因为它可以被拼接到更长的链中）。

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