如何高效计算双列表有效组合数并生成组合？优化低效Python代码

原代码的核心性能问题 #

你的代码耗时过长，主要根源在这几点：

1. 无用计算冗余：生成了所有元素的组合（包括完全不含P的无效组合），再做过滤，做了大量没必要的遍历。
2. 重复检查效率极低：每次生成子集后排序，再用sublist not in totalarray[L]做线性查找——当列表规模变大时，这个操作的时间复杂度会飙升到O(n)，严重拖慢速度。
3. 不必要的IO开销：循环中打印L的操作会占用额外系统资源。

优化思路 #

有效组合是「至少包含1个P元素的任意组合」，我们可以直接定向生成符合要求的组合，而非全量生成后过滤：

• 枚举从P中选取的元素数量（1到16个），从S中选取的元素数量（0到7个）
• 对每一组选取数量，生成对应的P子集和S子集，合并后就是有效组合
• 利用itertools.combinations的特性：生成的子集本身按原列表顺序排列，提前让P和S有序，合并后的组合自然有序，无需额外排序
• 这种方式不会生成重复组合，完全不需要重复检查

优化后的代码 #

import itertools

P_num = 16
S_num = 7

# 提前生成有序的P、S列表，保证组合合并后自然有序，避免额外排序
P = [f"P{i}" for i in range(1, P_num + 1)]
S = [f"S{i}" for i in range(1, S_num + 1)]

# 按组合长度分组存储结果
totalarray = {length: [] for length in range(1, P_num + S_num + 1)}

# 枚举从P中选取k个元素（k≥1）
for k in range(1, P_num + 1):
    p_combs = itertools.combinations(P, k)
    # 枚举从S中选取m个元素（m≥0）
    for m in range(0, S_num + 1):
        if m == 0:
            # 仅选P元素的情况，直接加入对应长度的列表
            for p_subset in p_combs:
                totalarray[k].append(list(p_subset))
        else:
            s_combs = itertools.combinations(S, m)
            # 合并P子集和S子集，生成有效组合
            for p_subset in p_combs:
                for s_subset in s_combs:
                    combined = p_subset + s_subset
                    totalarray[k + m].append(list(combined))
            # 重置p_combs迭代器，避免迭代器耗尽
            p_combs = itertools.combinations(P, k)

# 统计并输出结果
total = 0
for length in sorted(totalarray.keys()):
    count = len(totalarray[length])
    print(f"长度{length}: {count}个组合")
    total += count

print(f"总有效组合数: {total}")

额外优化：仅统计组合数（无需生成实际组合） #

如果只需要计算总组合数，不需要生成具体的组合列表，可以直接用数学公式计算，速度极快：
总有效组合数 = (2^P_num - 1) * (2^S_num)

• P元素有2^{16种选择方式，减去全不选的1种，得到至少选1个P的情况：2}16 - 1 = 65535
• S元素有2^{7种选择方式（包括全不选）：2}7 = 128
• 两者相乘得到总有效组合数：65535 * 128 = 8388480

对应的极简代码：

P_num = 16
S_num = 7

total = (2 ** P_num - 1) * (2 ** S_num)
print(f"总有效组合数: {total}")

内容的提问来源于stack exchange，提问作者E.Plail