【算法求解】n个英雄y把武器，有多少种组合方式包括空手的状态？

Question

题目描述

一共有n个英雄，地上有y把武器，可以赤手空拳，求解算法怎么高效的获取所有组合方式

相关代码

public function mock(): array
{
    $a = ["A","B","C"]; //英雄
    $b = [1,2,3,4];//武器
    
    //A0表示赤手空拳

    return [
        "A0,B1,C2","A0,B1,C3","A0,B1,C4","A0,B2,C1","A0,B2,C3","A0,B2,C4",
        "A0,B3,C2","A0,B3,C1","A0,B3,C4","A0,B4,C2","A0,B4,C3","A0,B4,C1",
        //......
        "A1,B2,C3","A1,B2,C4","A1,B3,C2","A1,B3,C4","A1,B4,C2","A1,B4,C3",
        "A2,B1,C3","A2,B1,C4","A2,B3,C1","A2,B3,C4","A2,B4,C1","A2,B4,C3",
        "A3,B1,C2","A3,B1,C4","A3,B2,C1","A3,B2,C4","A3,B4,C1","A3,B4,C2",
        "A4,B1,C2","A4,B1,C3","A4,B2,C1","A4,B2,C3","A4,B3,C1","A4,B3,C2",
    ];
}

求解算法或者解题思路，拜谢

Answer 1

首先确定最终有x个人获得了武器，\( x \in [0, max\{y, n\}] \)
其次确定这x个人持有的x把武器，然后对武器进行分配（关心顺序），最终枚举x获得答案

$$ \sum_{x=0}^{max(y, n)} {n \choose x}{y \choose x}A_x^x $$

Answer 2

看你的描述英雄似乎不能拿多于一把武器，那么有：

• 第1把武器可以分给n个英雄中任意一个，所以有n种可能
• 第2把武器可以分给n-1个英雄中任意一个，所以有n-1种可能
  ...
• 第y把武器可以分给n-y+1个英雄中任意一个，所以有n-y+1种可能

根据乘法原理，最终的组合数是： n * (n-1) * ... (n-y+1)