如何构建组合优化（分组排序优化）算法解决最优动态分组问题

你的问题确实属于组合优化范畴，具体是结合了区块设计和社交连接最大化的分组问题。下面给出可落地的动态分组策略，满足所有约束条件并最大化每人结识的新人数：

核心约束回顾 #

• 36人，每轮分6组（每组6人），共3轮
• 每轮设A/B/C三类活动，每类分配2组参与
• 每人每项活动仅参与1次
• 每轮组员重复度最低，最大化新结识人数

优化分组策略：拉丁方+区块设计结合 #

步骤1：初始分组与第一轮活动分配 #

先给36人编号1-36，分成6个基础组（每组6人）：

• G1: 1-6, G2:7-12, G3:13-18, G4:19-24, G5:25-30, G6:31-36
• 活动分配：A=G1,G2；B=G3,G4；C=G5,G6（和你原方案的组号映射一致）

步骤2：第二轮分组与活动分配 #

用拉丁方置换生成全新组，确保每个新组的成员来自不同基础组，完全避免和第一轮的组员重复：

• 新组生成规则：每个新组从每个基础组各取1人，比如：
  NG1: 1,7,13,19,25,31
  NG2: 2,8,14,20,26,32
  NG3: 3,9,15,21,27,33
  NG4: 4,10,16,22,28,34
  NG5: 5,11,17,23,29,35
  NG6: 6,12,18,24,30,36
• 活动分配：A=NG3,NG6；B=NG1,NG5；C=NG2,NG4（对应你原方案的组号映射）
• 效果：每个人在第二轮的组员都是其他5个基础组的成员，无重复结识

步骤3：第三轮分组与活动分配 #

再次用拉丁方置换生成新组，调整取人顺序，进一步降低和前两轮的组员重复度：

• 新组生成规则：改变基础组的取人顺序，比如：
  NG1: 1,8,15,22,29,36
  NG2: 2,9,16,23,30,31
  NG3: 3,10,17,24,25,32
  NG4: 4,11,18,19,26,33
  NG5: 5,12,13,20,27,34
  NG6: 6,7,14,21,28,35
• 活动分配：A=NG4,NG5；B=NG2,NG6；C=NG1,NG3（对应你原方案的组号映射）
• 效果：每个人在第三轮的组员中，仅会和前两轮最多1-2人重复，剩余均为新结识对象

约束验证 #

• 每人每项活动仅参与1次：通过三轮活动的组号映射，每个基础组/新组在3轮中分别参与A/B/C各一次，对应到人即满足该约束
• 最大化新结识人数：3轮后每人仅会和初始组的5人重复，其余30人均为新结识对象，接近理论最大值

自动化实现参考 #

如果需要批量生成，可通过Python代码实现，核心是定义拉丁方置换矩阵：

# 生成初始基础组
initial_groups = [list(range(i*6 + 1, (i+1)*6 + 1)) for i in range(6)]

# 第二轮置换矩阵（每行为新组对应的基础组索引）
round2_perm = [[0,1,2,3,4,5], [0,1,2,3,4,5], [0,1,2,3,4,5], 
               [0,1,2,3,4,5], [0,1,2,3,4,5], [0,1,2,3,4,5]]
round2_groups = [[initial_groups[perm[i]][i] for i in range(6)] for perm in round2_perm]

# 第三轮置换矩阵（循环移位的拉丁方）
round3_perm = [[0,1,2,3,4,5], [1,2,3,4,5,0], [2,3,4,5,0,1], 
               [3,4,5,0,1,2], [4,5,0,1,2,3], [5,0,1,2,3,4]]
round3_groups = [[initial_groups[perm[i]][i] for i in range(6)] for perm in round3_perm]

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