JavaScript生成飞行棋合法移动的所有数组组合方案问询

递归实现方案 #

以下递归方案可生成所有符合规则的移动组合，支持任意长度的棋子数组和骰子数组。核心思路是逐个处理每个骰子，将其分配给任意一个棋子，递归完成剩余骰子的分配，直到所有骰子都被分配完毕。

const generateAllMoves = (tokens, diceValues) => {
    const result = [];

    // 递归函数：处理剩余骰子，维护当前分配状态
    const recurse = (remainingDice, currentAssignment) => {
        // 终止条件：所有骰子分配完成，记录结果
        if (remainingDice.length === 0) {
            // 转换为和你代码一致的数组格式（每个元素是单个棋子的分配对象）
            const move = Object.entries(currentAssignment).map(([token, dice]) => ({ [token]: dice }));
            result.push(move);
            return;
        }

        const currentDie = remainingDice[0];
        const restDice = remainingDice.slice(1);

        // 遍历所有棋子，尝试将当前骰子分配给它
        for (const token of tokens) {
            // 复制当前分配状态，避免修改原对象
            const newAssignment = { ...currentAssignment };
            if (newAssignment[token]) {
                // 该棋子已有分配，追加当前骰子
                newAssignment[token] = [...newAssignment[token], currentDie];
            } else {
                // 该棋子未分配，新建数组存储当前骰子
                newAssignment[token] = [currentDie];
            }
            // 递归处理剩余骰子
            recurse(restDice, newAssignment);
        }
    };

    // 启动递归：初始状态无分配，传入全部骰子
    recurse(diceValues, {});
    return result;
};

// 示例调用
const tokens = ['A', 'B', 'C', 'D'];
const diceValues = [1, 3, 4, 6];
const allValidMoves = generateAllMoves(tokens, diceValues);
console.log(`总合法组合数：${allValidMoves.length}`); // 输出256

方案说明 #

• 递归过程中每次只处理一个骰子，确保所有骰子都会被分配，满足规则1；
• 允许将多个骰子分配给同一个棋子，也可以只用单个棋子分配全部骰子，满足规则2；
• 通过复制分配状态的方式避免递归中的副作用，保证每个分支的独立性；
• 输出格式和你当前代码的格式一致（数组内每个元素是单个棋子的分配对象），方便后续使用。

合法组合数的数学计算方法 #

核心公式 #

假设棋子数量为m，骰子数量为n，总合法组合数为：

总组合数 = m^n

即m的n次方。

原理 #

每个骰子可以独立分配给任意一个棋子，共有m种选择；n个骰子的选择相互独立，因此总组合数是m乘以自身n次。

验证示例 #

对于你的场景：m=4（4个棋子），n=4（4个骰子），总组合数为4^4=256，和递归代码的输出结果一致。

特殊情况说明 #

如果你的需求是每个棋子最多分配一组骰子（即每个棋子要么不分配，要么分配一个非空骰子子集，不能多次分配），则组合数需要用第二类斯特林数计算：

总组合数 = Σ（k=1到min(m,n)）[S(n,k) * P(m,k)]

• S(n,k)：第二类斯特林数，代表将n个骰子分成k个非空子集的方式数；
• P(m,k)：排列数，代表从m个棋子中选k个进行排列的方式数（子集分配给不同棋子算不同组合）。
  不过根据你给出的规则，该特殊情况不符合需求，因此优先使用m^n的公式。

对你当前代码的问题分析 #

你当前的嵌套循环方案仅覆盖了将骰子分成两组的情况，遗漏了以下合法组合：

• 单个棋子分配全部骰子（1组）；
• 骰子分成3组分配给3个棋子；
• 骰子分成4组分配给4个棋子；
  递归方案则通过逐个分配骰子的方式，自然覆盖了所有可能的分组和分配情况，不会遗漏任何合法组合。

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