均匀随机生成一个由 k 个无符号整数组成的向量，总和为 N

Question

另一种说法是：将 N 个相同的项目随机划分到 k 个桶中，并允许某些桶为空。

对于本次讨论：

• “N 的整数分区”，为了匹配通常的定义和计数，可以被认为是：
  • 一个正整数元组，按降序排列，总和为 N
• 无符号整数向量是 N 的“分区”，如果其元素之和（没有整数溢出）为 N。

我想编写一个函数 f(N,k) ，它在长度为 k 的可能向量中随机且均匀地进行选择，对 N 进行分区并返回所选向量。

如果有一个适用于所有 k>=1 的解决方案，那就太好了，但我对 k > N 特别感兴趣。因此，如果它有助于集中或限制该条件，那就可以了。如果我们必须深入研究近似/启发法，可以考虑 k 足够大，以至于大多数向量条目必须为零（因此至少 k > 2N）。

---

我最初的想法是：

1. 如果 N 足够小，可以合理地计算（或在表中查找？）N 的整数分区数，那么也许我们可以继续：
   • 创建一个由 k 个无符号整数组成的向量，初始化为零
   • 对 N 进行随机整数划分。令 m 为该元组的长度。
   • 将这些值放置在向量的初始 m 个位置。
   • 随机打乱向量。

这会天真地认为输出向量中包含 N 的一个条目的可能性与包含 1 的 N 个条目的可能性相同。这是不正确的。但也许有一个简单的权重可以应用于“制作 N 的随机整数分区”，从而纠正这个问题？

2. 另一种方法感觉更干净，但可能仍然需要在某个地方“重新加权”：
   • 创建一个由 k 个无符号整数组成的向量，初始化为零
   • 执行以下N次：
     • 随机选择向量的一个元素并递增它

虽然开始时感觉更干净，但我认为尝试“重新加权”会更加混乱。虽然第 1 部分的权重对我来说听起来像是一个困难的算法问题，但我至少可以想象需要计算什么。在这里，我什至不确定什么需要重新加权以及如何重新加权。

我认为它可能仍然需要重新加权的原因是，恰好有一个随机选择序列会导致向量看起来像 [N,0,0,...,0]，并且 N！随机选择序列将导致向量以 N 个 [1,1,...,1,0,0,...,0] 开头。计算最终结果的这些“不正确权重”的比率听起来是可行的，但我不知道如何重新权衡各个步骤来纠正它。

3. 或者也许还有另一种完全是我没有想到的方法？

Answer 1

生成 0-n k-1 次范围内的随机 int。将它们视为 [1, 1, ..., 1] 的分区 <- size n. Then the sums between partitions (& endpoints) are your vector.

例如，n=2，k=5：

假设我们得到 0, 1, 1, 2

我们将其视为：[|1||1|]

我们将其解释为 [0, 1, 0, 1, 0]（将间隙视为零）。

如果我们有 0,0,2,2，我们就会有 [||1,1||] 或 [0,0,2,0,0]