Python3中如何快速判断列表是否为列表集合中某列表的子集

问题场景 #

我有两个列表：一个是整数列表，另一个由整数列表组成。示例如下：

a = [1,2,3]
b = [[1,2,5],[1,4,7],[1,2,3,5]]

需要在Python 3中快速判断a是否为b中任意一个列表的子集。上述示例应返回True（因为a是b最后一个列表的子集）；若b为[[1,2,4],[1,4,7],[2,3,5]]，则返回False。

我知道可以将所有列表转为集合后逐个检查，但由于列表规模较大（b包含数十万个无重复列表）且需频繁执行该操作，希望找到更高效的实现方式。补充说明：a与b中的列表均包含0至1000之间的无重复整数。

目前我的实现代码：

def check_sublist(a,b):
   for list in b:
      if set(a) <= set(list):
         return True
   return False

高效解决方案 #

由于元素范围固定在0-1000，**二进制掩码（位图）**是最优方案：将每个列表转换为一个整数，用二进制位标记元素是否存在（数值x对应整数的第x位设为1）。子集判断可简化为位运算：a的掩码 & b中某列表的掩码 == a的掩码，该操作是CPU原生支持的，速度远快于集合子集判断。

具体实现步骤 #

1. 预处理b：将b中的所有列表提前转换为掩码整数，避免重复转换（仅需执行一次）。
2. 转换a为掩码：每次检查时仅需转换一次a。
3. 位运算判断：遍历预处理后的掩码集合，验证是否存在满足条件的掩码。

基础优化代码 #

def list_to_mask(lst):
    mask = 0
    for num in lst:
        mask |= 1 << num
    return mask

# 预先处理b，仅执行一次
b_masks = {list_to_mask(sublist) for sublist in b}

def check_subset(a, b_masks):
    a_mask = list_to_mask(a)
    for b_mask in b_masks:
        if (a_mask & b_mask) == a_mask:
            return True
    return False

进一步优化：过滤候选掩码 #

如果b中某个列表的元素数量少于a，则它不可能包含a作为子集。可以按元素个数对b的掩码分组，检查时仅遍历元素数量≥a长度的分组，减少遍历次数：

from collections import defaultdict

# 预处理b，按子列表长度分组存储掩码
b_masks_by_length = defaultdict(set)
for sublist in b:
    mask = list_to_mask(sublist)
    b_masks_by_length[len(sublist)].add(mask)

def check_subset_optimized(a, b_masks_by_length):
    a_len = len(a)
    a_mask = list_to_mask(a)
    # 仅检查元素数量足够的分组
    for length in b_masks_by_length:
        if length >= a_len:
            for b_mask in b_masks_by_length[length]:
                if (a_mask & b_mask) == a_mask:
                    return True
    return False

方案优势 #

• 位运算速度远快于集合操作，适合频繁执行的场景
• 预处理仅需一次，后续检查的时间成本极低
• 0-1000的元素范围对应1001位的整数，Python原生支持大整数，无溢出问题

测试验证 #

针对原示例：

a = [1,2,3]
b = [[1,2,5],[1,4,7],[1,2,3,5]]
# 转换后a的掩码为14（2+4+8），b中最后一个列表的掩码为46（2+4+8+32）
# 14 & 46 ==14，满足条件，返回True

针对返回False的案例：

b = [[1,2,4],[1,4,7],[2,3,5]]
# 各子列表掩码分别为22、146、44，与14的位运算结果均不等于14，返回False

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