实现序列子集合并为超集并统计关联数量的函数开发需求

需求说明 #

输入为嵌套列表，示例输入：

input = [['A'], ['A', 'B'], ['A', 'B', 'C'], ['A', 'B'], ['X', 'Y'], ['A', 'B', 'C'], ['X'], ['A'], ['X', 'A', 'B']]

需实现函数完成以下目标：

• 从输入中筛选出最大超集：不存在其他输入列表能以顺序匹配的方式包含该列表（即该列表无法作为子集被其他输入列表包含）。
• 统计每个最大超集对应的符合条件的子集数量（包括自身、重复项及所有顺序匹配的子集），被合并的子集不再出现在最终输出中。

核心逻辑 #

1. 子集匹配规则 #

定义is_subsequence函数判断列表subset是否是superset的顺序匹配子集，提供两种实现：

• 前缀匹配（示例默认规则）：子集是超集的前k个元素，顺序完全一致。
• 广义子序列匹配：子集元素按顺序出现在超集中，不要求连续。

def is_subsequence(subset, superset):
    # 前缀匹配实现
    if len(subset) > len(superset):
        return False
    return superset[:len(subset)] == subset

# 广义子序列匹配实现</think_never_used_51bce0c785ca2f68081bfa7d91973934></think_never_used_51bce0c785ca2f68081bfa7d91973934># 序列超集归约与计数函数实现

## 需求说明
输入为嵌套列表，示例输入：
```python
input = [['A'], ['A', 'B'], ['A', 'B', 'C'], ['A', 'B'], ['X', 'Y'], ['A', 'B', 'C'], ['X'], ['A'], ['X', 'A', 'B']]

需实现函数完成以下目标：

• 从输入中筛选出最大超集：不存在其他输入列表能以顺序匹配的方式包含该列表（即该列表无法作为子集被其他输入列表包含）。
• 统计每个最大超集对应的符合条件的子集数量（包括自身、重复项及所有顺序匹配的子集），被合并的子集不再出现在最终输出中。

核心逻辑 #

1. 子集匹配规则 #

定义is_subsequence函数判断列表subset是否是superset的顺序匹配子集，提供两种实现：

• 前缀匹配（示例默认规则）：子集是超集的前k个元素，顺序完全一致。
• 广义子序列匹配：子集元素按顺序出现在超集中，不要求连续。

def is_subsequence(subset, superset):
    # 前缀匹配实现
    if len(subset) > len(superset):
        return False
    return superset[:len(subset)] == subset

# 广义子序列匹配实现（按需替换）
# def is_subsequence(subset, superset):
#     it = iter(superset)
#     return all(item in it for item in subset)

2. 函数实现（不重复统计版本） #

该版本确保每个子集仅被分配到包含它的最长超集中，总计数之和等于输入元素总数，符合“被合并的子集不再重复统计”的要求。

from collections import defaultdict

def reduce_to_max_supersets(input_list):
    # 统计每个唯一列表的出现次数（用元组作为字典键，列表不可哈希）
    count_map = defaultdict(int)
    for lst in input_list:
        count_map[tuple(lst)] += 1
    unique_lists = list(count_map.keys())
    
    # 按列表长度降序排序，优先处理更长的列表
    unique_lists.sort(key=lambda x: len(x), reverse=True)
    
    assigned = set()  # 记录已被分配到超集的列表
    result = {}
    
    for candidate in unique_lists:
        if candidate in assigned:
            continue
        # 当前候选为最大超集，统计所有未被分配且能被它包含的列表的总次数
        total_count = 0
        for subset in unique_lists:
            if subset in assigned:
                continue
            if is_subsequence(subset, candidate):
                total_count += count_map[subset]
                assigned.add(subset)
        # 转回列表作为结果的键（若需可哈希键，可保留元组）
        result[list(candidate)] = total_count
    
    return result

3. 函数实现（重复统计版本） #

该版本统计每个最大超集能覆盖的所有子集数量（包括被其他超集覆盖的子集），总计数之和可能大于输入元素总数，适用于需要统计超集覆盖范围的场景。

from collections import defaultdict

def reduce_to_max_supersets_duplicate_count(input_list):
    count_map = defaultdict(int)
    for lst in input_list:
        count_map[tuple(lst)] += 1
    unique_lists = list(count_map.keys())
    
    # 筛选最大超集：不存在其他列表能包含该列表
    max_supersets = []
    for candidate in unique_lists:
        is_max = True
        for other in unique_lists:
            if candidate == other:
                continue
            if is_subsequence(candidate, other):
                is_max = False
                break
        if is_max:
            max_supersets.append(candidate)
    
    # 统计每个最大超集覆盖的所有子集的总次数
    result = {}
    for superset in max_supersets:
        total_count = 0
        for subset in unique_lists:
            if is_subsequence(subset, superset):
                total_count += count_map[subset]
        result[list(superset)] = total_count
    
    return result

测试示例 #

不重复统计版本输出 #

input = [['A'], ['A', 'B'], ['A', 'B', 'C'], ['A', 'B'], ['X', 'Y'], ['A', 'B', 'C'], ['X'], ['A'], ['X', 'A', 'B']]
print(reduce_to_max_supersets(input))
# 输出：{'A', 'B', 'C']: 6, ['X', 'A', 'B']: 2, ['X', 'Y']: 1}

• 计数说明：
  • ['A','B','C']覆盖自身（2次）、['A','B']（2次）、['A']（2次），总计6次。
  • ['X','A','B']覆盖自身（1次）、['X']（1次），总计2次。
  • ['X','Y']仅覆盖自身（1次），总计1次。

重复统计版本输出 #

print(reduce_to_max_supersets_duplicate_count(input))
# 输出：{'A', 'B', 'C']: 6, ['X', 'Y']: 2, ['X', 'A', 'B']: 2}

• 计数说明：
  • ['X','Y']覆盖自身（1次）、['X']（1次），总计2次。
  • ['X','A','B']覆盖自身（1次）、['X']（1次），总计2次。
  • 注：此版本中['X']被两个超集同时统计，总计数之和为6+2+2=10，大于输入元素总数9。

性能优化说明 #

针对数千条数据的场景，当前实现的时间复杂度为O(n²)，可通过以下方式优化：

• 对列表按长度分组，仅在更长的列表中检查是否包含当前列表。
• 使用前缀树（Trie）结构存储所有列表，快速查找包含当前列表的超集或被当前列表包含的子集。

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