Python求解带分类选取约束的嵌套列表幂集实现方法

解决方案 #

核心思路 #

你要的组合本质是每个分类独立选择「不选」或「选该分类下任意1个元素」，总组合数计算规则为所有分类的(元素数量+1)相乘后，减去全不选的1种无效组合，你的示例刚好符合这个计算逻辑：(2+1)*(1+1)*(1+1)*(1+1) - 1 = 23。
我们可以用itertools.product求笛卡尔积直接生成所有符合规则的组合，没有多余算力浪费。

实现代码 #

from itertools import product

# 你已经生成的分类字典
dic = {'A': ['a1', 'a3'], 'B': ['b4'], 'C': ['c4'], 'D': ['d6']}

# 为每个分类添加「不选」的占位选项
category_choices = [[None] + items for items in dic.values()]

# 求所有分类选项的笛卡尔积
result = []
for combo in product(*category_choices):
    # 过滤掉空元素和全不选的无效组合
    valid = [item for item in combo if item is not None]
    if valid:
        result.append(set(valid))

结果验证 #

print(len(result))
# 输出 23，符合预期
print(result[:5])
# 输出 [{'a1'}, {'a1', 'b4'}, {'a1', 'c4'}, {'a1', 'b4', 'c4'}, {'a1', 'd6'}]，和你给出的示例匹配

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