士兵优先选择最少占用营房的住宿排列数计算问题求解

需要实现符合以下选房规则的住宿安排计数函数：

• 士兵归营选择营房时，始终优先选择当前入住人数最少的营房
• 若存在多个人数并列最少的营房，则从中随机选择入住
• 入参为S（士兵总数量）、B（营房总数量），返回符合规则的住宿安排总数量
• 校验基准：S=3、B=2时，无约束全排列共6种，符合上述规则的正确结果为4种

原有Java代码实现的是无规则约束下的全排列计数，没有加入选房优先级约束，因此计算结果和预期不符。

不需要做全量排列枚举，利用规则的对称性逐轮递推即可，时间复杂度为O(S*B)：

1. 初始状态所有营房入住人数为0，逐轮安排士兵入住
2. 每轮安排前，先找到当前营房的最少入住人数，统计有多少个营房符合这个最少人数要求，记为k
3. 当前士兵有k种合法选择，将k乘到总方案数中
4. 由于同人数的营房完全对称，无论选哪个人数最少的营房，后续的可选方案数都不会变化，因此随便选一个符合要求的营房更新入住人数即可，不需要模拟随机分支

注：该逻辑默认士兵、营房均为不同个体，符合常规排列计数要求。

Javascript版本 #

function possibleArrangements(S, B) {
    if (B === 0) return 0;
    if (S === 0) return 1;
    // 初始化每个营房的入住人数
    const barracks = new Array(B).fill(0);
    let total = 1;

    for (let i = 0; i < S; i++) {
        // 查找当前最少入住人数
        const minCount = Math.min(...barracks);
        // 统计人数最少的营房数量
        const minBarracksCount = barracks.filter(cnt => cnt === minCount).length;
        // 累计当前步的可选方案数
        total *= minBarracksCount;
        // 任选一个人数最少的营房更新人数（对称场景下不影响计数结果）
        const targetIndex = barracks.findIndex(cnt => cnt === minCount);
        barracks[targetIndex]++;
    }

    return total;
}

修正后的Java版本 #

public class Main {
    /**
     * @param S 士兵总数量
     * @param B 营房总数量
     * @return 符合选房规则的住宿安排总数
     */
    static public long possibleArrangements(int S, int B) {
        if (B == 0) return 0;
        if (S == 0) return 1;
        
        int[] barracks = new int[B];
        long total = 1;

        for (int i = 0; i < S; i++) {
            // 查找当前最少入住人数
            int minCount = Integer.MAX_VALUE;
            for (int cnt : barracks) {
                if (cnt < minCount) minCount = cnt;
            }

            // 统计人数最少的营房数量，同时记录第一个符合要求的营房索引
            int minBarracksCount = 0;
            int firstMinIndex = -1;
            for (int j = 0; j < B; j++) {
                if (barracks[j] == minCount) {
                    minBarracksCount++;
                    if (firstMinIndex == -1) firstMinIndex = j;
                }
            }

            // 累计当前步的可选方案数
            total *= minBarracksCount;
            // 更新选中营房的入住人数
            barracks[firstMinIndex]++;
        }

        return total;
    }

    public static void main(String[] args) {
        System.out.println(possibleArrangements(2,2)); // 输出2
        System.out.println(possibleArrangements(3,2)); // 输出4，符合预期
        System.out.println(possibleArrangements(4,3)); // 输出18
    }
}

• S=2,B=2时返回2，符合预期
• S=3,B=2时返回4，和规则要求的结果一致
• S=4,B=3时返回18，对应每步可选数为3→2→1→3，乘积321*3=18

内容的提问来源于stack exchange，提问作者Talha Bin Fahim