Python字典中列表去重与唯一子序列提取技术问询

嘿，我来帮你搞定这个序列处理的问题！分两步走，先搞定元素顺序无关的去重，再处理相似边界的子序列提取～

第一步：筛选元素顺序无关的唯一列表 #

要判断两个列表是否属于「元素相同、顺序无关」的重复，核心思路是把每个列表转换成不可变的无序结构（比如frozenset），用集合记录已经出现过的“特征标识”，遍历过程中只保留第一次出现的原列表。

下面是Python实现代码：

# 示例输入字典，键可自定义，值为待处理的序列列表
original_dict = {
    "seq1": [1, 2, 3],
    "seq2": [3, 2, 1],  # 和seq1元素完全一致，属于重复
    "seq3": [2, 3, 4],
    "seq4": [4, 2, 3],  # 和seq3元素完全一致，属于重复
    "seq5": [5, 6],
    "seq6": [6, 5]       # 和seq5元素完全一致，属于重复
}

seen_signatures = set()
unique_lists = []

# 遍历字典中的所有列表，筛选唯一项
for lst in original_dict.values():
    # 生成列表的无序特征标识（元素顺序不影响）
    lst_signature = frozenset(lst)
    if lst_signature not in seen_signatures:
        seen_signatures.add(lst_signature)
        unique_lists.append(lst)

# 输出结果
print("筛选后的唯一列表：")
for idx, lst in enumerate(unique_lists, 1):
    print(f"第{idx}个列表：{lst}")

这段代码会保留每个元素组合的首次出现列表，比如示例中最终会得到[1,2,3]、[2,3,4]、[5,6]三个唯一列表。

第二步：依据顺序相似性提取唯一子序列 #

这里我们用**最长公共子序列（LCS）**来定义「元素顺序相似性」——LCS就是两个列表中元素顺序完全一致的公共部分，也就是我们要找的“边界”。提取边界之外的部分，就是两个列表的唯一子序列。

比如针对你提到的「第1个和第3个列表的边界」，可以用以下代码实现：

def longest_common_subsequence(a, b):
    # 动态规划计算最长公共子序列
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # 回溯构造正序的LCS
    i, j = m, n
    lcs = []
    while i > 0 and j > 0:
        if a[i-1] == b[j-1]:
            lcs.append(a[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return lcs[::-1]

def extract_unique_subseq(lst, boundary):
    # 从原列表中移除边界部分，保留剩余的唯一子序列（原顺序不变）
    boundary_iter = iter(boundary)
    current_bound_elem = next(boundary_iter, None)
    unique_subseq = []
    for elem in lst:
        if elem == current_bound_elem:
            current_bound_elem = next(boundary_iter, None)
        else:
            unique_subseq.append(elem)
    return unique_subseq

# 用第一步得到的唯一列表举例（替换成你的实际数据）
list1 = [1, 2, 3, 4]
list3 = [2, 3, 5, 6]

# 计算两个列表的边界（LCS）
boundary = longest_common_subsequence(list1, list3)
print(f"第1个和第3个列表的边界（顺序相似区域）：{boundary}")

# 提取各自的唯一子序列
unique_subseq1 = extract_unique_subseq(list1, boundary)
unique_subseq3 = extract_unique_subseq(list3, boundary)

print(f"第1个列表的唯一子序列：{unique_subseq1}")
print(f"第3个列表的唯一子序列：{unique_subseq3}")

运行这段代码后，示例中的边界是[2,3]，提取出的唯一子序列分别是[1,4]和[5,6]，正好是两个列表中顺序不重叠的独有部分。如果你的「顺序相似性」指的是连续公共子串，把LCS换成最长公共子串的计算逻辑即可，原理是相通的～

内容的提问来源于stack exchange，提问作者My Little Tulpa