本文介绍如何将54名学生按偏好（互选关系）分配到14间3人房和6间2人房中，通过构建加权图、枚举合法房间组合并评分排序，实现可解释、可扩展的近似最优分配方案。
这是一个典型的带偏好约束的组合分配问题，本质是将学生划分为固定大小（2人或3人）且互不重叠的子集，同时最大化群体满意度。由于硬性约束明确（恰好6个双人间 + 14个三人间 = 54人），而偏好具有对称性（如A喜欢B且B喜欢A才构成有效匹配），我们可将其建模为加权超图划分问题，并采用“生成-过滤-评分”三步策略高效求解。
核心思路：图建模 + 合法组合生成 + 加权评估
构建无向加权图
每位学生为一个节点；若两人互为偏好（即 B in preferences[A] and A in preferences[B]），则在它们之间添加一条权重为 +2 的边；否则设为 -1（表示低兼容性）。注意：必须验证双向偏好，单向喜欢不能保证共住意愿。-
生成所有合法房间候选
- 所有满足互惠偏好的2人组合 → 双人间候选集 pairs
- 所有满足两两互惠的3人组合（即三角形子图）→ 三人间候选集 triples
使用 itertools.combinations(students, 2) 和 itertools.combinations(students, 3) 枚举，并用集合交集快速验证：
def is_valid_pair(a, b, prefs):
return b in prefs.get(a, []) and a in prefs.get(b, [])
def is_valid_triple(a, b, c, prefs):
return (is_valid_pair(a, b, prefs) and
is_valid_pair(b, c, prefs) and
is_valid_pair(a, c, prefs))-
构造全局分配方案并过滤合法性
直接枚举所有从 pairs ∪ triples 中选出6个pair + 14个triple的组合，计算量爆炸（不可行）。更优策略是：
✅ 先生成所有可能的 单个房间（pair/triple）及其得分；
✅ 再使用回溯或约束编程（如 python-constraint 或 ortools）进行精确匹配；
⚠️ 若规模可控（如 ≤30人），可改用 itertools.product 分层采样 + is_allowed() 过滤（见原答案中 defaultdict 计数逻辑）。
以下为轻量级可行实现（适配原题54人场景，含剪枝）：
from itertools import combinations, product
from collections import Counter
# 假设已预计算好 valid_pairs 和 valid_triples 列表，每个元素为 tuple + score
# e.g., valid_pairs = [(('A','B'), 4), (('C','D'), 3), ...]
# valid_triples = [(('A','B','C'), 9), ...]
def score_room(group, prefs):
s = 0
for a, b in combinations(group, 2):
s += 2 if (b in prefs.get(a, []) and a in prefs.get(b, [])) else -1
return s
# 预生成（建议用多进程加速）
valid_pairs = [
(pair, score_room(pair, preferences))
for pair in combinations(students, 2)
if is_valid_pair(*pair, preferences)
]
valid_triples = [
(triple, score_room(triple, preferences))
for triple in combinations(students, 3)
if is_valid_triple(*triple, preferences)
]
# 关键剪枝：仅保留高分候选（如 top 500 pairs & top 1000 triples）
valid_pairs = sorted(valid_pairs, key=lambda x: x[1], reverse=True)[:500]
valid_triples = sorted(valid_triples, key=lambda x: x[1], reverse=True)[:1000]
# 枚举分配：选择6个pair + 14个triple，覆盖全部54人且无重复
best_score, best_assignment = -float('inf'), None
for pairs_combo in combinations(valid_pairs, 6):
used = set()
for p, _ in pairs_combo:
used.update(p)
if len(used) != 12: continue # 必须恰好12人
remaining = set(students) - used
for triples_combo in combinations(valid_triples, 14):
all_in_triples = set()
for t, _ in triples_combo:
all_in_triples.update(t)
if all_in_triples == remaining:
total_score = sum(s for _, s in pairs_combo) + sum(s for _, s in triples_combo)
if total_score > best_score:
best_score = total_score
best_assignment = (pairs_combo, triples_combo)
print("✅ Optimal assignment found!")
print("2-bed rooms:", [p for p, _ in best_assignment[0]])
print("3-bed rooms:", [t for t, _ in best_assignment[1]])
print("Total happiness score:", best_score)注意事项与进阶建议
- 时间复杂度警示：纯暴力枚举在54人下不可行（C(54,2)≈1400对，C(54,3)≈24k个三人组），务必配合预筛选 + 分数阈值剪枝 + 启发式采样；
- 偏好数据清洗：原始 preferences 字典需统一键名、去重、补全空列表，避免 KeyError；
-
替代方案推荐：
- ✅ 整数规划（IP）：用 ortools.linear_solver 建模为0-1变量（x_ij=1 表示i,j同房），添加容量与覆盖约束；
- ✅ 图聚类启发式：将学生视为节点，偏好强度为边权，用 networkx.algorithms.community.greedy_modularity_communities 初步分组，再按大小调整；
- ✅ 模拟退火 / 遗传算法：定义邻域操作（如交换两人房间、拆分重组三元组），以总分作为适应度函数；
- 公平性补充：可在目标函数中加入方差惩罚项，避免出现“全高分房+全低分房”的极端分配。
最终，该问题不是单纯算法题，而是建模能力 + 工程权衡 + 领域理解的综合体现——优先保证约束满足（人数/房间数/互惠性），再追求满意度最大化。
