无偏小队分队算法问询：多人游戏固定人数分队机制优化

核心问题拆解 #

原算法的关键缺陷是：当A队剩余空间无法容纳任何小队时，直接将这类小队全部分配至B队，导致小队成员的入选概率为0；同时只能从单排玩家中补位，使得单排玩家的入选概率远高于x/N，完全违背了“所有玩家入选概率相同”的要求。

可行解决方案 #

核心思路 #

通过全局规划小队的入选概率，结合单排玩家的动态补选，同时满足三个核心要求：A队人数恰好为x、小队整体分配、每个玩家入选A队的概率严格等于x/N。

具体步骤 #

1. 预处理分组

   • 将玩家分为单排集合S（规模记为s）和小队列表Q（每个小队规模为q_i，所有小队总人数记为t，满足s + t = N）。

2. 确定小队入选概率

   • 每个小队的入选概率设为p_i = x/N，以此保证小队中每个玩家的基础入选概率为x/N。

3. 随机筛选入选小队

   • 对每个小队生成0到1之间的随机数r_i：若r_i ≤ p_i，则该小队入选A队；否则分配至B队。
   • 统计入选小队的总人数k = sum(q_i for 入选的小队)。若k > x，则重新生成随机数筛选小队，直到k ≤ x（拒绝采样避免总人数超额）。

4. 补选单排玩家凑齐名额

   • 计算A队剩余名额m = x - k，从单排集合S中随机抽取m个玩家加入A队。
   • 剩余未入选的单排玩家和小队全部分配至B队。

方案验证（用户案例） #

以N=100、x=25，含1个4人小队、96名单排玩家为例：

• 小队入选概率为25/100=0.25：
  • 若小队入选，需从单排中选21人，单排玩家的入选概率为0.25*(21/96)；
  • 若小队不入选，需从单排中选25人，单排玩家的入选概率为0.75*(25/96)；
  • 单排玩家总入选概率：(0.25*21 + 0.75*25)/96 = 24/96 = 0.25，与小队成员入选概率一致；
  • A队人数始终为25，完全符合要求。

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