如何生成学生导师项目分配场景下assignment problem的cost matrix

解决方案 #

你原来的代码生成拉丁方的核心原因是用了循环移位+全排列的逻辑，天然强制了每行、每列的数值无重复，只要放弃这套逻辑，改成逐行按照你的打分规则生成即可，完全满足“同一项目允许不同学生打相同分数”的要求。

调整后的代码 #

import random

def create_score_matrix(student_num, project_num, prefer_num=5, null_score=999):
    matrix = []
    for _ in range(student_num):
        # 初始化当前学生所有项目的分数为缺省值（代表未打分）
        row = [null_score] * project_num
        # 随机选出prefer_num个该学生的偏好项目
        selected_projects = random.sample(range(project_num), prefer_num)
        # 生成1~prefer_num的不重复随机分数（对应1-5的打分）
        scores = random.sample(range(1, prefer_num+1), prefer_num)
        # 填充分数到对应项目位置
        for proj_idx, score in zip(selected_projects, scores):
            row[proj_idx] = score
        matrix.append(row)
    return matrix

调用示例 #

1. 小维度测试（5×5矩阵）

N = 5
test_matrix = create_score_matrix(N, N, prefer_num=5, null_score=-1)
for row in test_matrix:
    print(row)

输出示例（可看到同一列存在重复分数）：

[3, 1, 2, 5, 4]
[1, 4, 3, 2, 5]
[3, 5, 1, 2, 4]
[2, 3, 5, 4, 1]
[5, 1, 4, 3, 2]

2. 实际场景调用（130学生、250项目）

# 未打分项目用999标记，方便后续cost计算
actual_matrix = create_score_matrix(student_num=130, project_num=250, prefer_num=5, null_score=999)

补充说明 #

如果后续需要关联导师分配规则，可以额外生成一张项目-导师映射表，将每个项目绑定到对应负责导师，即可把学生对项目的打分转换为对导师的偏好分，再结合单导师最多带12人的约束做分配计算即可。

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