带数量上下限的多产品合法组合生成算法优化咨询

性能问题根源 #

原有方案通过跨品类无差别合并单品类条目，会大量生成同品类数量叠加超出最大值的无效结果，还需要额外做合法性校验，相当于把N个独立的数量选择问题转化为了无规则的排列组合，凭空产生了数个量级的无效计算。

最优实现思路 #

采用按品类独立遍历合法数量+笛卡尔积拼接的方案，全程不会生成任何无效组合，所有输出结果100%符合约束要求，计算量和合法结果的数量完全对等。
具体步骤如下：

1. 为每个品类单独生成合法取值数组，仅存储数量值即可，无需预生成重复的产品实例，大幅节省预计算开销和内存占用。比如示例中的三个品类对应合法数量数组为：
   • Product1: [1,2]
   • Product2: [2,3]
   • Product3: [1,2]
2. 对所有品类的合法数量数组做笛卡尔积计算，每个输出的元组就是对应品类的选取数量，所有元组天然符合单品类的数量约束，无需额外校验。示例中总共有222=8个合法的数量组合，不存在任何无效项。
3. 若需要生成带具体产品实例的列表，再根据每个数量元组，将对应数量的产品实例拼入结果即可。

代码示例（Python） #

# 配置每个产品的最小、最大选取数量
product_config = {
    "Product1": (1, 2),
    "Product2": (2, 3),
    "Product3": (1, 2)
}

# 预生成每个产品的合法数量列表
product_names = list(product_config.keys())
quantity_ranges = []
for min_q, max_q in product_config.values():
    quantity_ranges.append(range(min_q, max_q + 1))

# 生成所有合法组合
import itertools
all_valid_combinations = []
for quantities in itertools.product(*quantity_ranges):
    current_comb = []
    for name, qty in zip(product_names, quantities):
        current_comb.extend([name] * qty)
    all_valid_combinations.append(current_comb)

额外优化建议 #

• 若产品实例体积较大，可预存每个产品的单例对象，生成组合时直接重复引用即可，无需重复创建实例。
• 若品类数量极多、或单品类合法数量范围很大，可采用迭代器模式懒加载生成组合，无需一次性将所有结果存入内存。
• 若存在全局约束（比如所有产品总数量不能超过固定值），可在笛卡尔积遍历过程中做剪枝：当前已选品类的数量总和已经超出全局约束时，直接跳过后续品类的遍历分支，进一步减少计算量。

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