如何均匀随机生成和为N的k个无符号整数向量？

问题等价于：将N个相同物品随机分配到k个桶中，允许桶为空，要求均匀随机选取一种分配方案。

定义说明 #

• 常规整数分拆：一组降序排列的正整数元组，其和为N。
• 分拆向量：元素和为N的k维无符号整数向量（无整数溢出）。

需求 #

实现函数f(N,k)，从所有符合条件的k维向量中均匀随机选取一个返回。需适配所有k≥1的场景，重点覆盖k>N甚至k>2N（此时向量多数元素为0）的情况，可采用精确方案或近似/启发式方案。

初始思路与存在的问题 #

1. 基于整数分拆的方法（仅适用于N较小时）

   • 步骤：初始化k个0的向量→随机生成N的整数分拆（长度m）→将分拆值放入前m个位置→随机打乱向量
   • 问题：错误地认为[N,0,...,0]与[1,1,...,1,0,...,0]的出现概率相等，需对整数分拆的随机生成添加权重修正，否则无法保证均匀性。

2. 逐次加1的方法

   • 步骤：初始化k个0的向量→重复N次随机选一个元素加1
   • 问题：生成[N,0,...,0]仅有一种选择序列，而生成含N个1的向量有N!种序列，导致结果权重偏差，且暂未找到有效的修正方式。

3. 疑问：是否存在其他可行的实现思路？

可行实现方案 #

方法1：隔板法（精确均匀，适配所有k≥1） #

基于组合数学中的隔板法，将N个物品分配到k个桶（允许空）的方案数为组合数C(N+k-1, k-1)，每个方案对应唯一的分拆向量，可通过随机生成组合索引构造向量：

1. 生成k-1个不重复的随机整数，取值范围为[0, N+k-1)，将其排序得到x₀ < x₁ < ... < x_{k-2}
2. 计算向量各元素：
   • 第一个元素：x₀
   • 中间元素（第i个，1 ≤ i ≤ k-2）：xᵢ - x_{i-1} - 1
   • 最后一个元素：(N+k-1) - x_{k-2} - 1
3. 最终得到的向量即为均匀随机的符合条件的分拆向量。

方法2：k>N场景的高效精确方案 #

当k远大于N时，大部分元素为0，可优化步骤减少计算量：

1. 按权重随机选择非零桶的数量t：t的取值范围为1 ≤ t ≤ min(N,k)，每个t对应的权重为C(k,t) * C(N-1, t-1)（即选t个桶的组合数乘以N个物品分配到t个非空桶的方案数）
2. 从k个桶中随机无放回选择t个桶
3. 对这t个桶分配N个物品（不允许空）：生成t-1个[1, N-1]范围内的不重复随机数，排序后计算每个桶的物品数量（类似隔板法）
4. 将计算得到的数值放入选中的t个桶，其余桶填充0，得到最终向量。

方法3：k>>2N时的近似方案 #

当k远大于2N（如k是N的10倍以上），大部分桶必然为0，可采用近似方案降低计算成本：

1. 生成N个独立的随机桶索引（取值范围[0, k-1]），统计每个桶被选中的次数
2. 由于k极大，重复选中同一桶的概率极低，得到的向量与均匀分布的偏差可忽略；若需更高精度，可对出现多次的桶进行少量调整，但通常无需额外处理。

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