Python实现平均分均衡的分组：从高低中分集合构建小组

你的需求是将高、中、低三组各6名学生配对成6个小组，每组包含三组各一名学生，且小组平均分尽可能均衡。用itertools暴力枚举所有排列不可行（组合数达51万+，规模再大直接爆炸），以下是几种高效的实现方案：

一、贪心策略（快速实现，效果尚可） #

核心思路是通过排序交叉配对，拉平每组总分：将高分组降序排列，中分组升序、低分组降序交叉配对，让高分搭配较低的中/低分，低分搭配较高的中/低分，尽量平衡总分。

代码实现 #

high = [401.2,398.8,350.2,288.3,263.3,249.8]
mid = [249.6,246.7,244.2,239.8,211.4,204.9]
low = [203.5,165.9,157.7,135.3,129.1,100.9]

# 排序：高分组降序，中分组升序，低分组降序
high_sorted = sorted(high, reverse=True)
mid_sorted = sorted(mid)
low_sorted = sorted(low, reverse=True)

# 按索引一一配对
groups = list(zip(high_sorted, mid_sorted, low_sorted))

# 输出结果
print("贪心配对结果：")
for idx, (h, m, l) in enumerate(groups, 1):
    total = h + m + l
    print(f"小组{idx}: 高={h}, 中={m}, 低={l}, 总分={total:.2f}, 平均分={total/3:.2f}")

这种方法优点是代码简单、运行快，缺点是不一定能得到全局最优解，但对于你的场景已经能得到不错的均衡效果。

二、模拟退火算法（启发式寻优，接近最优） #

如果需要更均衡的结果，可以用模拟退火算法在解空间中搜索最优配对，它能跳出局部最优，找到接近全局最优的解，适合中等规模的分组问题。

代码实现 #

import random
import math

high = [401.2,398.8,350.2,288.3,263.3,249.8]
mid = [249.6,246.7,244.2,239.8,211.4,204.9]
low = [203.5,165.9,157.7,135.3,129.1,100.9]
group_count = len(high)
total_sum = sum(high) + sum(mid) + sum(low)
target_avg = total_sum / group_count

# 计算当前分组的方差（方差越小越均衡）
def calc_variance(groups):
    scores = [sum(g) for g in groups]
    mean = sum(scores) / group_count
    return sum((s - mean)**2 for s in scores) / group_count

# 生成初始随机配对
def init_solution():
    mid_perm = random.sample(mid, group_count)
    low_perm = random.sample(low, group_count)
    return list(zip(high, mid_perm, low_perm))

# 生成邻域解：交换两个中分组或低分组的位置
def neighbor_solution(current):
    mid_list = [g[1] for g in current]
    low_list = [g[2] for g in current]
    
    if random.random() < 0.5:
        # 交换中分组的两个元素
        i, j = random.sample(range(group_count), 2)
        mid_list[i], mid_list[j] = mid_list[j], mid_list[i]
    else:
        # 交换低分组的两个元素
        i, j = random.sample(range(group_count), 2)
        low_list[i], low_list[j] = low_list[j], low_list[i]
    
    return list(zip(high, mid_list, low_list))

# 模拟退火主逻辑
def simulated_annealing(init_temp=1000, cool_rate=0.995, iterations=10000):
    current_sol = init_solution()
    current_var = calc_variance(current_sol)
    best_sol, best_var = current_sol, current_var
    temp = init_temp
    
    for _ in range(iterations):
        new_sol = neighbor_solution(current_sol)
        new_var = calc_variance(new_sol)
        
        # 接受更优解，或按概率接受较差解
        if new_var < current_var:
            current_sol, current_var = new_sol, new_var
            if new_var < best_var:
                best_sol, best_var = new_sol, new_var
        else:
            accept_prob = math.exp((current_var - new_var) / temp)
            if random.random() < accept_prob:
                current_sol, current_var = new_sol, new_var
        
        temp *= cool_rate
    
    return best_sol, best_var

# 运行算法并输出结果
best_groups, best_var = simulated_annealing()
print("\n模拟退火最优结果：")
for idx, (h, m, l) in enumerate(best_groups, 1):
    total = h + m + l
    print(f"小组{idx}: 高={h}, 中={m}, 低={l}, 总分={total:.2f}, 平均分={total/3:.2f}")
print(f"分组方差（越小越均衡）：{best_var:.2f}")

三、整数规划（全局最优，适合小规模场景） #

如果需要严格的全局最优解，可以用整数规划构建模型，通过求解器找到最优配对。这种方法适合分组规模较小的场景（比如你的6组），规模大了计算会变慢。

代码实现（需要安装pulp库：pip install pulp） #

from pulp import LpProblem, LpVariable, LpMinimize, lpSum, value

high = [401.2,398.8,350.2,288.3,263.3,249.8]
mid = [249.6,246.7,244.2,239.8,211.4,204.9]
low = [203.5,165.9,157.7,135.3,129.1,100.9]
n = len(high)

# 定义问题：最小化总分的平方和（等价于最小化方差）
prob = LpProblem("BalanceGroups", LpMinimize)

# 变量：y[i][j] = 1 表示高分组第i个学生配对中分组第j个
y = [[LpVariable(f"y_{i}_{j}", cat='Binary') for j in range(n)] for i in range(n)]
# 变量：z[i][k] = 1 表示高分组第i个学生配对低分组第k个
z = [[LpVariable(f"z_{i}_{k}", cat='Binary') for k in range(n)] for i in range(n)]

# 目标函数：最小化所有小组总分的平方和
prob += lpSum(
    (high[i] + lpSum(mid[j]*y[i][j] for j in range(n)) + lpSum(low[k]*z[i][k] for k in range(n)))**2
    for i in range(n)
)

# 约束：每个高分组学生只能配对一个中分组学生
for i in range(n):
    prob += lpSum(y[i][j] for j in range(n)) == 1
# 每个中分组学生只能被一个高分组学生配对
for j in range(n):
    prob += lpSum(y[i][j] for i in range(n)) == 1

# 约束：每个高分组学生只能配对一个低分组学生
for i in range(n):
    prob += lpSum(z[i][k] for k in range(n)) == 1
# 每个低分组学生只能被一个高分组学生配对
for k in range(n):
    prob += lpSum(z[i][k] for i in range(n)) == 1

# 求解
prob.solve()

# 提取结果
groups = []
for i in range(n):
    # 找到配对的中分组学生
    j = next(j for j in range(n) if value(y[i][j]) == 1)
    # 找到配对的低分组学生
    k = next(k for k in range(n) if value(z[i][k]) == 1)
    groups.append( (high[i], mid[j], low[k]) )

# 输出结果
print("\n整数规划最优结果：")
for idx, (h, m, l) in enumerate(groups, 1):
    total = h + m + l
    print(f"小组{idx}: 高={h}, 中={m}, 低={l}, 总分={total:.2f}, 平均分={total/3:.2f}")
scores = [sum(g) for g in groups]
variance = sum((s - sum(scores)/n)**2 for s in scores)/n
print(f"分组方差：{variance:.2f}")

为什么itertools不适合？ #

如果用itertools.permutations生成中分组和低分组的所有排列，组合数是6! * 6! = 720 * 720 = 518400种，虽然这个数量级能跑，但效率极低，而且如果分组规模扩大到10组，组合数会变成10!*10! ≈ 3.6e12，完全无法处理。所以必须用上述更高效的算法。

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