Python中筛选超集的极大子集：算法优化方案问询

问题描述 #

给定某超集的若干子集，需要筛选出所有极大子集——即不被任何其他子集包含的子集，排除所有被其他子集包含的子集。

输入示例 #

['/img0.jpg']
['/img1.jpg']
['/img10.jpg']
['/img11.jpg', '/img9.jpg']
['/img12.jpg', '/img15.jpg']
['/img11.jpg', '/img13.jpg', '/img8.jpg', '/img9.jpg']
['/img14.jpg']
['/img15.jpg']
['/img16.jpg']
['/img14.jpg', '/img17.jpg']
['/img18.jpg']
['/img19.jpg', '/img22.jpg']
['/img2.jpg']
['/img19.jpg', '/img20.jpg', '/img21.jpg', '/img22.jpg']
['/img19.jpg', '/img21.jpg', '/img22.jpg']
['/img22.jpg']
['/img23.jpg']
['/img3.jpg']
['/img3.jpg', '/img4.jpg']
['/img0.jpg', '/img5.jpg']
['/img6.jpg']
['/img2.jpg', '/img7.jpg']
['/img11.jpg', '/img8.jpg', '/img9.jpg']
['/img9.jpg']

期望输出 #

['/img1.jpg']
['/img10.jpg']
['/img11.jpg', '/img13.jpg', '/img8.jpg', '/img9.jpg']
['/img12.jpg', '/img15.jpg']
['/img14.jpg', '/img17.jpg']
['/img16.jpg']
['/img18.jpg']
['/img19.jpg', '/img20.jpg', '/img21.jpg', '/img22.jpg']
['/img2.jpg', '/img7.jpg']
['/img23.jpg']
['/img3.jpg', '/img4.jpg']
['/img0.jpg', '/img5.jpg']
['/img6.jpg']

现有代码问题 #

你提供的代码存在两个核心问题：

1. 结果不准确：代码逻辑是生成每个子集的所有超集元素并集，而非筛选极大子集，导致输出大量重复结果。
2. 性能低下：双重循环遍历所有子集对，且每次都将子集转成set，时间复杂度为O(n²*k)（n是子集数量，k是子集平均大小），内存开销也较高。

算法思路与实现 #

核心思路 #

极大子集的判定标准是：不存在其他子集完全包含当前子集。基于这个标准，有两种主要优化方向：

思路1：排序优化+Set快速判定

1. 先将所有子集按元素数量降序排序：大子集不可能被小子集包含，排序后只需检查当前子集是否被已筛选出的极大子集包含，无需再和后面的小子集比较。
2. 遍历排序后的子集，对每个子集，检查是否存在已保留的极大子集完全包含它：
   • 若不存在，则将其加入极大子集列表；
   • 若存在，则跳过。

实现代码：

def find_maximal_subsets(subsets):
    # 去除空子集，按子集长度降序排序
    sorted_subsets = sorted([s for s in subsets if s], key=lambda x: -len(x))
    maximal = []
    
    for subset in sorted_subsets:
        subset_set = set(subset)
        is_maximal = True
        # 检查当前子集是否被已有的极大子集包含
        for m in maximal:
            if subset_set.issubset(set(m)):
                is_maximal = False
                break
        if is_maximal:
            maximal.append(subset)
    return maximal

# 测试输入
input_subsets = [
    ['/img0.jpg'], ['/img1.jpg'], ['/img10.jpg'],
    ['/img11.jpg', '/img9.jpg'], ['/img12.jpg', '/img15.jpg'],
    ['/img11.jpg', '/img13.jpg', '/img8.jpg', '/img9.jpg'],
    ['/img14.jpg'], ['/img15.jpg'], ['/img16.jpg'],
    ['/img14.jpg', '/img17.jpg'], ['/img18.jpg'],
    ['/img19.jpg', '/img22.jpg'], ['/img2.jpg'],
    ['/img19.jpg', '/img20.jpg', '/img21.jpg', '/img22.jpg'],
    ['/img19.jpg', '/img21.jpg', '/img22.jpg'], ['/img22.jpg'],
    ['/img23.jpg'], ['/img3.jpg'], ['/img3.jpg', '/img4.jpg'],
    ['/img0.jpg', '/img5.jpg'], ['/img6.jpg'], ['/img2.jpg', '/img7.jpg'],
    ['/img11.jpg', '/img8.jpg', '/img9.jpg'], ['/img9.jpg']
]

result = find_maximal_subsets(input_subsets)
for s in result:
    print(s)

思路2：不用Set的实现（排序+双指针）

如果不想用set，可以通过子集内部排序+双指针的方式判断包含关系：

1. 先将每个子集内部的元素排序，同时将所有子集按长度降序排序。
2. 对于两个排序后的子集A和B，用双指针遍历：若A的所有元素都能在B中按顺序找到，则A是B的子集。

这种方法避免了set的内存开销，适合元素可排序的场景。

实现代码：

def is_subset(a, b):
    # a和b都是已排序的列表，判断a是否是b的子集
    ptr_a = ptr_b = 0
    len_a, len_b = len(a), len(b)
    while ptr_a < len_a and ptr_b < len_b:
        if a[ptr_a] == b[ptr_b]:
            ptr_a += 1
        ptr_b += 1
    return ptr_a == len_a

def find_maximal_subsets_no_set(subsets):
    # 每个子集内部排序，同时按子集长度降序排序
    sorted_subsets = sorted(
        [sorted(s) for s in subsets if s],
        key=lambda x: -len(x)
    )
    maximal = []
    
    for subset in sorted_subsets:
        is_maximal = True
        for m in maximal:
            if is_subset(subset, m):
                is_maximal = False
                break
        if is_maximal:
            maximal.append(subset)
    return maximal

# 测试
result = find_maximal_subsets_no_set(input_subsets)
for s in result:
    print(s)

进一步优化（针对大数据量） #

如果子集数量极大，可以采用哈希表+元素计数的方式：

1. 给每个元素分配唯一ID，将子集转换为元素ID的集合。
2. 用位掩码表示子集（仅当元素总数不超过64时可用，用整数或bitarray），此时子集包含关系可通过位运算(a & b) == a快速判断，时间复杂度降到O(n²)。

优化后结果 #

上述两种方法都能输出符合要求的极大子集，且性能远优于原代码：

• 避免了重复结果；
• 排序后减少了无效比较；
• 不用Set的版本节省了set转换的内存开销。

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