Python生成不同规模队伍的全部唯一组合并筛选最高得分队伍

核心实现思路 #

• 先做前置合法性校验：总人数n必须满足3*num_teams ≤ n ≤ 5*num_teams，否则不存在符合人数要求的队伍组合，直接返回空即可
• 用带剪枝的回溯法生成所有无重复的合法组合：为了避免生成重复的同构组合（比如队内人员顺序不同、队伍顺序不同都属于同一个组合），每次选人固定按人员索引升序选择，保证每个组合仅生成一次
• 回溯过程中实时剪枝：如果剩余未分配人数无法满足剩余队伍的最低总人数要求，或者超过剩余队伍的最高总人数限制，直接终止当前分支的递归，减少无效计算
• 每生成一个完整的合法队伍组合，调用得分函数计算得分，同步更新全局最优解

完整代码实现 #

from itertools import combinations

# 可自定义替换为实际的得分计算逻辑
def calculate_score(teams):
    # 示例得分：可根据你的业务需求修改，比如按技能匹配度、兼容性等计算
    score = 0
    for team in teams:
        score += len(team) * 10 # 示例逻辑：人数多的队得分更高，可自行替换
    return score

def generate_best_teams(people, num_teams):
    n = len(people)
    # 前置校验：人数是否符合队伍规模要求
    if not (3 * num_teams <= n <= 5 * num_teams):
        raise ValueError("总人数不符合3-5人每队的分配要求")
    
    best_score = float('-inf')
    best_teams = None
    # 转换为索引处理，避免人员重名问题，同时方便去重
    people_indices = list(range(n))

    def backtrack(remaining_indices, formed_teams):
        nonlocal best_score, best_teams
        remaining_teams = num_teams - len(formed_teams)
        # 所有队伍已生成，计算得分
        if remaining_teams == 0:
            if not remaining_indices:
                current_teams = [[people[i] for i in team] for team in formed_teams]
                current_score = calculate_score(current_teams)
                if current_score > best_score:
                    best_score = current_score
                    best_teams = current_teams
            return
        
        # 剪枝：剩余人数不符合剩余队伍的规模要求
        remaining_count = len(remaining_indices)
        if remaining_count < 3 * remaining_teams or remaining_count > 5 * remaining_teams:
            return
        
        # 固定选第一个未分配的人作为当前队的第一个成员，避免组合重复
        first_idx = remaining_indices[0]
        other_candidates = remaining_indices[1:]
        # 当前队人数可以是3、4、5人，减去已经选的1个，还要选2-4个
        for select_count in range(2, min(4, len(other_candidates)) + 1):
            for members in combinations(other_candidates, select_count):
                current_team = [first_idx] + list(members)
                # 剩下的未分配索引
                new_remaining = [i for i in remaining_indices if i not in current_team]
                backtrack(new_remaining, formed_teams + [current_team])
    
    backtrack(people_indices, [])
    return best_teams, best_score

# 示例调用
if __name__ == "__main__":
    people = ["Bob", "Jane", "Mary", "Martha", "James", "Charles", "Kevin", "Debbie", "Brian", "Matt", "Milo", "Chris", "Sam"]
    best_teams, best_score = generate_best_teams(people, 4)
    print("最优队伍组合：")
    for team in best_teams:
        print(team)
    print(f"最高得分：{best_score}")

注意事项 #

• 代码中默认生成的组合不会出现重复的同构情况，不需要额外去重
• 如果人员规模较大（比如超过20人分5队以上），全量遍历的计算量会急剧上升，此时建议替换为启发式算法（比如遗传算法、模拟退火）来近似求解最优解
• calculate_score函数可根据你的实际需求自定义，比如按技能互补、人员熟悉度等维度计算得分

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