如何检查列表中元组的字符串或其子集是否存在于其他列表

需求说明 #

需要实现以下功能：

• 检查列表中元组（格式为(组标识, 字符串)）是否存在于另一个目标列表中
• 同时验证该元组中字符串的任意非空子集（保持组标识不变，字符串由原字符串的任意子序列组成，比如C1C2C8C9的子集包括C1C2、C1C8、C2C9等）组成的同结构元组是否存在于目标列表
• 对每个输入列表中的所有元组执行上述检查

原始数据 #

三个待处理的列表：

list1 = [('g1', 'C1C2C8C9'), ('g2', 'C5C6'), ('g3', 'C3C4'), ('g5', 'C1C3C7'), ('g1g5', 'C1'), ('g3g5', 'C3'), ('g4g5', 'C7')]
list2 = [('g1', 'C3C4C5C7'), ('g3', 'C1C2C6C8C9'), ('g4', 'C1C2C3C4C6'), ('g3g4', 'C1'), ('g3g4', 'C2'), ('g1g4', 'C3'), ('g1g4', 'C4'), ('g3g4', 'C6'), ('g2g3', 'C8'), ('g3g5', 'C9')]
list3 = [('g1', 'C1C2C3C4C5C7C8C9'), ('g2', 'C1C2C5C6C7C8'), ('g3', 'C1C2C5C7'), ('g4', 'C1C2C5C6C7'), ('g5', 'C1C2C5C7C9'), ('g1g4g3g2g5', 'C1'), ('g5g2g4g3g1', 'C2'), ('g5g2g4g1g3', 'C5'), ('g4g2', 'C6'), ('g5g2g4g3g1', 'C7'), ('g2g1', 'C8'), ('g1g5', 'C9')]

示例场景 #

以元组('g1', 'C1C2C8C9')为例：

1. 先检查该元组本身是否存在于目标列表（比如list3）
2. 再检查所有由C1C2C8C9的任意子序列组成的同结构元组，如('g1', 'C1C2')、('g1', 'C1C8')、('g1', 'C2C9')、('g1', 'C1')等是否存在于目标列表

当前实现方案（效果不佳） #

import textwrap as tw
lfd = []
for lists in run_all(matrix_3):
    #print(lists)
    l = []
    for tup in lists:
        if len(tup[1])>2:
            lt1=tw.wrap(tup[1],2)
            for c1 in lt1:
                tupl1=(tup[0],c1)
                l.append(tupl1)
        elif len(tup[1])<=2 and len(tup[0])>2:
            lt0=tw.wrap(tup[0],2)
            for c0 in lt0:
                tupl0=(c0,tup[1])
                l.append(tupl0)
    lfd.append(l)
print(lfd)

优化思路与实现 #

步骤1：预处理目标列表，构建快速查询集合 #

为了避免每次检查都遍历目标列表，先将目标列表中的元组转换为集合，这样查询操作的时间复杂度从O(n)降为O(1)：

# 预处理目标列表为集合
target_set = set(list3)

步骤2：生成字符串的所有非空子集 #

对于元组中的字符串（比如C1C2C8C9），需要先拆分出单个元素（如['C1', 'C2', 'C8', 'C9']），然后生成所有非空子集的字符串组合：

from itertools import combinations

def get_all_substrings(s):
    # 拆分字符串为单个元素（每个元素是两位，如'C1'）
    elements = [s[i:i+2] for i in range(0, len(s), 2)]
    substrings = []
    # 生成所有长度>=1的组合
    for length in range(1, len(elements)+1):
        for combo in combinations(elements, length):
            substrings.append(''.join(combo))
    return substrings

步骤3：批量检查元组及其子集的存在性 #

遍历输入列表中的每个元组，生成所有子集元组后，批量检查是否存在于目标集合中：

def check_tuple_and_subsets(input_tuple, target_set):
    group_id, s = input_tuple
    # 检查原元组是否存在
    original_exists = input_tuple in target_set
    # 生成所有子集字符串
    subset_strings = get_all_substrings(s)
    # 生成所有子集元组
    subset_tuples = [(group_id, sub_str) for sub_str in subset_strings]
    # 检查每个子集元组的存在性，返回结果字典
    subset_exists = {t: t in target_set for t in subset_tuples}
    return {
        'original_tuple': input_tuple,
        'original_exists': original_exists,
        'subset_checks': subset_exists
    }

# 示例：检查list1中的所有元组
results = []
for t in list1:
    res = check_tuple_and_subsets(t, target_set)
    results.append(res)

# 打印结果
for res in results:
    print(f"原元组: {res['original_tuple']}，是否存在: {res['original_exists']}")
    print("子集检查结果:")
    for subset, exists in res['subset_checks'].items():
        print(f"  {subset}: {'存在' if exists else '不存在'}")
    print("-"*50)

优化点说明 #

1. 查询效率提升：使用集合存储目标元组，将查询操作从线性遍历转为哈希查找，大幅提升性能
2. 完整子集覆盖：通过itertools.combinations生成所有非空子集，避免遗漏任何可能的子组合
3. 结果结构化：返回清晰的检查结果，便于后续分析和处理
4. 通用性强：函数可复用，适用于任意符合格式的输入元组和目标列表

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