如何处理教师班级分配对象？求简易算法解决方案

问题描述 #

你需要处理一个班级与预注册教师的映射对象，实现教师到班级的一对一分配，输入结构示例如下：

{
     Class1: {Teacher1: '333333', Teacher2: '000000', Teacher3: '444444'},
     Class2: {Teacher1: '000000', Teacher2: '111111', Teacher3: '444444'},
     Class3: {Teacher1: '444444', Teacher2: '555555'},
     Class4: {Teacher1: '222222', Teacher2: '000000'},
     Class5: {Teacher1: '333333'},
     Class6: {Teacher1: '111111', Teacher2: '000000'}
}

分配需遵循以下规则：

• 1名教师对应1个班级（一对一匹配）
• 若班级仅注册1名教师，则直接选定该教师
• 若教师仅注册1个班级，则将该教师分配至该班级
• 存在多种可行方案时，随机选择其一
• 无法分配时返回false，否则返回结果对象

预期结果示例（仅展示部分可行方案）：

{
    Class1: '000000',
    Class2: '444444',
    Class3: '555555',
    Class4: '222222',
    Class5: '333333',
    Class6: '111111',
}

简易解决思路 #

这本质是二分图匹配问题，但为了让你快速实现，我们用贪心预处理+随机尝试补全的方案，不需要复杂算法知识，步骤清晰：

步骤1：预处理数据 #

先把输入转换成更易操作的格式：

• 把每个班级的可选教师提取为数组（比如Class1: ['333333', '000000', '444444']）
• 统计每个教师被多少个班级列为可选（比如'333333'对应2个班级）

步骤2：强制分配确定项 #

循环处理以下两种情况，直到没有可强制分配的项：

1. 单教师班级：如果某个班级只剩1个可选教师，直接分配该教师，同时把这个教师从其他所有班级的可选列表中移除，并更新教师的统计数。
2. 单班级教师：如果某个教师只剩1个可选班级，直接分配该教师到这个班级，同时清空该班级的其他可选教师，并更新班级的可选列表。

步骤3：随机补全剩余匹配 #

经过预处理后，剩余的班级和教师都有多个可选选项，我们可以：

• 打乱剩余班级的顺序（保证随机性）
• 逐个给班级分配未被占用的可选教师，如果遇到无法分配的情况，重新随机尝试几次；如果多次尝试都失败，返回false。

代码实现（JavaScript） #

function assignTeachers(classTeachers) {
    // 预处理：转换格式并统计教师出现次数
    const classOptions = {};
    const teacherClassCount = {};
    const allTeachers = new Set();

    // 初始化数据
    for (const className of Object.keys(classTeachers)) {
        const teachers = Object.values(classTeachers[className]);
        classOptions[className] = [...teachers];
        teachers.forEach(t => {
            teacherClassCount[t] = (teacherClassCount[t] || 0) + 1;
            allTeachers.add(t);
        });
    }

    const assigned = {};
    const usedTeachers = new Set();

    // 步骤2：处理强制分配项，循环直到没有可处理的项
    let hasChanges;
    do {
        hasChanges = false;

        // 处理单教师班级
        for (const className of Object.keys(classOptions)) {
            if (assigned[className]) continue;
            const options = classOptions[className];
            // 过滤掉已被使用的教师
            const available = options.filter(t => !usedTeachers.has(t));
            if (available.length === 1) {
                const teacher = available[0];
                assigned[className] = teacher;
                usedTeachers.add(teacher);
                // 更新其他班级的可选列表和教师统计
                for (const otherClass of Object.keys(classOptions)) {
                    if (otherClass === className) continue;
                    const idx = classOptions[otherClass].indexOf(teacher);
                    if (idx !== -1) {
                        classOptions[otherClass].splice(idx, 1);
                        teacherClassCount[teacher]--;
                        hasChanges = true;
                    }
                }
            }
        }

        // 处理单班级教师
        for (const teacher of allTeachers) {
            if (usedTeachers.has(teacher)) continue;
            // 找到该教师还能选的未分配班级
            const possibleClasses = Object.keys(classOptions).filter(c => 
                !assigned[c] && classOptions[c].includes(teacher)
            );
            if (possibleClasses.length === 1) {
                const className = possibleClasses[0];
                assigned[className] = teacher;
                usedTeachers.add(teacher);
                // 清空该班级的其他可选教师
                classOptions[className] = [];
                hasChanges = true;
            }
        }
    } while (hasChanges);

    // 步骤3：随机补全剩余匹配
    const unassignedClasses = Object.keys(classOptions).filter(c => !assigned[c]);
    const availableTeachers = [...allTeachers].filter(t => !usedTeachers.has(t));

    // 如果剩余数量不匹配，直接返回false
    if (unassignedClasses.length !== availableTeachers.length) return false;

    // 尝试随机匹配，最多尝试5次避免死循环
    for (let attempt = 0; attempt < 5; attempt++) {
        const tempAssigned = {...assigned};
        const tempUsed = new Set(usedTeachers);
        const shuffledClasses = [...unassignedClasses].sort(() => Math.random() - 0.5);
        
        let success = true;
        for (const className of shuffledClasses) {
            // 找到该班级可选且未被使用的教师
            const validTeachers = classOptions[className].filter(t => !tempUsed.has(t));
            if (validTeachers.length === 0) {
                success = false;
                break;
            }
            // 随机选一个
            const selected = validTeachers[Math.floor(Math.random() * validTeachers.length)];
            tempAssigned[className] = selected;
            tempUsed.add(selected);
        }

        if (success) {
            return tempAssigned;
        }
    }

    // 多次尝试失败，返回false
    return false;
}

// 测试示例
const input = {
     Class1: {Teacher1: '333333', Teacher2: '000000', Teacher3: '444444'},
     Class2: {Teacher1: '000000', Teacher2: '111111', Teacher3: '444444'},
     Class3: {Teacher1: '444444', Teacher2: '555555'},
     Class4: {Teacher1: '222222', Teacher2: '000000'},
     Class5: {Teacher1: '333333'},
     Class6: {Teacher1: '111111', Teacher2: '000000'}
};

console.log(assignTeachers(input));

说明 #

• 这个实现先处理所有确定的分配，减少后续随机尝试的复杂度
• 随机尝试部分最多重试5次，既保证随机性，又避免无限循环
• 如果所有尝试都失败，说明不存在可行的分配方案，返回false

内容的提问来源于stack exchange，提问作者Khải Hồ Quang