多人游戏锦标赛玩家分组算法优化需求（MTG/Catan场景）

问题背景 #

需要为MTG、Catan这类锦标赛的玩家分组，要求每组人数在3-4人之间，核心目标是最小化轮空玩家数量。

现有代码采用手动近似分组逻辑，但存在明显局限性：仅能生成最多2个与目标规模不同的分组，无法处理需要多个非目标规模分组的场景（比如玩家总数为10人、目标组规模为4人时，最优分组是2个3人组+1个4人组，而原代码无法生成这类组合）。

现有算法逻辑 #

• 若玩家数可被targetPodSize整除，则平均分成若干目标规模组；
• 若余数与targetPodSize之和可平分且结果大于minPodSize，则拆分最后一组为两个等规模组；
• 若余数≥minPodSize，则先按目标规模分组，剩余玩家单独成组；
• 若余数与targetPodSize之和≤maxPodSize，则将剩余玩家合并到最后一个目标规模组中。

优化思路 #

核心是通过枚举所有符合人数范围的分组组合，找到覆盖所有玩家、满足minPodSize≤每组人数≤maxPodSize且轮空数为0（或最小）的最优方案：

1. 优先寻找无轮空的分组组合，针对3-4人的固定场景直接枚举3人组与4人组的数量搭配；
2. 通用场景下，通过计算组数量范围，分配平均人数并调整余数，生成符合要求的分组；
3. 若无法实现无轮空分组，计算最小轮空人数，确保轮空规模最小化。

优化后的Java代码 #

import java.util.ArrayList;
import java.util.List;

public class TournamentGrouping {

    public static List<GroupMatch> createGroupMatches(List<Player> players, int targetPodSize, int minPodSize, int maxPodSize) {
        if (targetPodSize < minPodSize || targetPodSize > maxPodSize) {
            throw new IllegalArgumentException("targetPodSize must be between minPodSize and maxPodSize");
        }

        List<Player> rankedPlayers = getClassification(players);
        int playerCount = rankedPlayers.size();
        List<GroupMatch> groupMatches = new ArrayList<>();

        // 优先寻找无轮空的最优分组方案
        GroupPlan plan = findOptimalGroupPlan(playerCount, minPodSize, maxPodSize);

        // 无完全分组方案时，返回最小轮空数（可根据需求调整为补充虚拟玩家逻辑）
        if (plan == null) {
            int minSkip = findMinSkipPlayers(playerCount, minPodSize, maxPodSize);
            throw new IllegalStateException("无法完全分组，最少需要轮空 " + minSkip + " 名玩家");
        }

        // 根据分组方案创建实际分组
        int currentIndex = 0;
        for (int size : plan.groupSizes) {
            groupMatches.add(new GroupMatch(rankedPlayers.subList(currentIndex, currentIndex + size)));
            currentIndex += size;
        }

        return groupMatches;
    }

    // 寻找无轮空的最优分组方案（优先贴近目标组规模）
    private static GroupPlan findOptimalGroupPlan(int totalPlayers, int minSize, int maxSize) {
        // 针对3-4人分组场景做专项优化
        if (minSize == 3 && maxSize == 4) {
            // 优先枚举目标规模的组（假设target为4，若target为3可调整顺序）
            for (int fourPlayerGroups = totalPlayers / 4; fourPlayerGroups >= 0; fourPlayerGroups--) {
                int remaining = totalPlayers - fourPlayerGroups * 4;
                if (remaining >= 0 && remaining % 3 == 0) {
                    List<Integer> sizes = new ArrayList<>();
                    for (int i = 0; i < fourPlayerGroups; i++) sizes.add(4);
                    for (int i = 0; i < remaining / 3; i++) sizes.add(3);
                    return new GroupPlan(sizes, 0);
                }
            }
            // 反向枚举确保覆盖所有可能
            for (int threePlayerGroups = totalPlayers / 3; threePlayerGroups >= 0; threePlayerGroups--) {
                int remaining = totalPlayers - threePlayerGroups * 3;
                if (remaining >= 0 && remaining % 4 == 0) {
                    List<Integer> sizes = new ArrayList<>();
                    for (int i = 0; i < threePlayerGroups; i++) sizes.add(3);
                    for (int i = 0; i < remaining / 4; i++) sizes.add(4);
                    return new GroupPlan(sizes, 0);
                }
            }
        } else {
            // 通用场景：枚举可能的组数量，生成符合范围的分组
            int maxGroups = totalPlayers / minSize;
            int minGroups = (totalPlayers + maxSize - 1) / maxSize;
            for (int groupCount = minGroups; groupCount <= maxGroups; groupCount++) {
                int avgSize = totalPlayers / groupCount;
                if (avgSize < minSize || avgSize > maxSize) continue;
                int remainder = totalPlayers % groupCount;
                List<Integer> sizes = new ArrayList<>();
                // 将余数分配给前remainder个组，每个组多1人
                for (int i = 0; i < remainder; i++) sizes.add(avgSize + 1);
                for (int i = remainder; i < groupCount; i++) sizes.add(avgSize);
                // 验证所有组规模是否符合要求
                boolean valid = true;
                for (int size : sizes) {
                    if (size < minSize || size > maxSize) {
                        valid = false;
                        break;
                    }
                }
                if (valid) return new GroupPlan(sizes, 0);
            }
        }
        return null;
    }

    // 计算最小轮空玩家数
    private static int findMinSkipPlayers(int totalPlayers, int minSize, int maxSize) {
        int skip = 0;
        while (true) {
            if (findOptimalGroupPlan(totalPlayers + skip, minSize, maxSize) != null) {
                return skip;
            }
            skip++;
        }
    }

    // 辅助类存储分组方案详情
    private static class GroupPlan {
        List<Integer> groupSizes;
        int skipCount;

        GroupPlan(List<Integer> groupSizes, int skipCount) {
            this.groupSizes = groupSizes;
            this.skipCount = skipCount;
        }
    }

    // 以下为假设的依赖类，需替换为项目真实实现
    public static class Player {}
    public static class GroupMatch {
        public GroupMatch(List<Player> players) {}
    }
    private static List<Player> getClassification(List<Player> players) {
        return new ArrayList<>(players);
    }
}

代码说明 #

1. 多非目标组支持：通过枚举所有合法分组组合，解决了原代码无法生成多个非目标规模分组的问题；
2. 场景适配：针对3-4人的常见锦标赛分组要求做了专项优化，提升计算效率；
3. 通用兼容：保留通用场景处理逻辑，支持任意minPodSize和maxPodSize配置；
4. 轮空处理：内置最小轮空数计算逻辑，明确告知无法完全分组时的最小轮空规模。

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