基于Pandas解决大学课程约束满足问题

问题背景 #

我们有一个存储大学课程信息的Pandas DataFrame，课程包含两类注册约束：

• 先修课程（pre-requisites）：必须提前修完才能注册目标课程
• 同期/先修课程（co-requisites）：可提前修完，也可与目标课程同期注册

约束覆盖多种场景：无约束课程、仅含同期约束课程、存在同期约束链的课程，且单门课程最多含1项同期约束。现有代码输入已修课程列表后，输出的可注册课程与预期不符：

• 已修课程示例：['微积分A', '微积分B', '线性代数', '物理A', '物理A实验', '物理B', '物理B实验']
• 当前代码输出：微积分C、计算机编程
• 预期输出：微积分C、微分方程、计算机编程、电路原理、电路原理实验

优化思路 #

核心是正确处理两类约束，尤其是同期约束的链状依赖：

1. 先修约束校验：目标课程的所有先修课程必须全部在已修列表中
2. 同期约束校验：
   • 若同期课程已修，直接满足条件
   • 若同期课程未修，但该同期课程本身的注册约束全部满足（即也可同期注册），则目标课程也允许注册

完整优化代码 #

import pandas as pd

def can_register(course_row, completed_courses, courses_df):
    # 校验先修课程约束
    pre_reqs = course_row['pre-requisites']
    if pd.notna(pre_reqs):
        pre_req_list = [req.strip() for req in pre_reqs.split(',')]
        if not all(req in completed_courses for req in pre_req_list):
            return False
    
    # 校验同期/先修课程约束
    co_req = course_row['co-requisites']
    if pd.notna(co_req):
        co_req = co_req.strip()
        # 情况1：同期课程已修
        if co_req in completed_courses:
            return True
        # 情况2：同期课程未修，但该课程也可同期注册
        co_req_row = courses_df[courses_df['course_name'] == co_req].iloc[0]
        if can_register(co_req_row, completed_courses, courses_df):
            return True
        # 两种情况都不满足，无法注册
        return False
    
    # 无任何约束，直接可注册
    return True

# 读取课程数据源
courses_df = pd.read_csv('courses.csv')
# 已修课程列表
completed_courses = ['微积分A', '微积分B', '线性代数', '物理A', '物理A实验', '物理B', '物理B实验']

# 筛选符合条件的可注册课程（排除已修课程）
registerable_courses = courses_df[courses_df.apply(
    lambda row: can_register(row, completed_courses, courses_df) and row['course_name'] not in completed_courses,
    axis=1
)]['course_name'].tolist()

# 输出结果
print("可注册课程：", registerable_courses)

验证结果 #

运行上述代码后，输出将完全匹配预期：

可注册课程： ['微积分C', '微分方程', '计算机编程', '电路原理', '电路原理实验']

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