Python如何编写考虑有限产量约束的生产排班全排列算法

核心思路 #

采用回溯法实现，在搜索过程中实时校验产量约束，自动剪枝不符合要求的分支，相比全枚举后过滤的方案效率更高。
首先明确所有约束条件：

• 单班次仅可从3种合法生产组合中选择，对应2条生产线同时开工：(A,B)、(A,C)、(B,C)
• 总班次固定为4
• 累计产量要求：A生产3次、B生产3次、C生产2次

Python实现代码 #

# 定义单班次所有可选生产组合
OPTIONS = [('A', 'B'), ('A', 'C'), ('B', 'C')]

def backtrack(remaining_shifts, left_a, left_b, left_c, current_path, result):
    # 终止条件：排满4个班次
    if remaining_shifts == 0:
        # 校验所有产品产量刚好达标
        if left_a == 0 and left_b == 0 and left_c == 0:
            result.append(current_path.copy())
        return
    # 遍历所有可选组合
    for opt in OPTIONS:
        need_a = 1 if 'A' in opt else 0
        need_b = 1 if 'B' in opt else 0
        need_c = 1 if 'C' in opt else 0
        # 剩余产量足够才进入下一层递归
        if left_a >= need_a and left_b >= need_b and left_c >= need_c:
            current_path.append(opt)
            backtrack(
                remaining_shifts - 1,
                left_a - need_a,
                left_b - need_b,
                left_c - need_c,
                current_path,
                result
            )
            # 回溯撤销选择
            current_path.pop()

# 格式化输出为示例格式的工具函数
def print_schedule(schedule):
    print("LineA LineB LineC")
    for shift in schedule:
        col_a = 'A' if 'A' in shift else '-'
        col_b = 'B' if 'B' in shift else '-'
        col_c = 'C' if 'C' in shift else '-'
        print(f"  {col_a}     {col_b}     {col_c}")

if __name__ == "__main__":
    all_schedules = []
    # 传入初始参数：剩余4个班次，A剩余3，B剩余3，C剩余2
    backtrack(4, 3, 3, 2, [], all_schedules)
    
    # 输出所有合法排班
    print(f"共找到{len(all_schedules)}种合法排班方案：")
    for idx, s in enumerate(all_schedules, 1):
        print(f"\n方案{idx}：")
        print_schedule(s)

结果验证 #

通过排列组合公式可计算合法排班总数：我们需要在4个班次中安排2次(A,B)、1次(A,C)、1次(B,C)，总排列数为 4!/(2!*1!*1!)=12，运行代码得到的结果长度刚好为12，符合预期。

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