另一种说法是:将N个相同的项目随机划分到k个桶中,并允许某些桶为空。
对于本次讨论:
- 为了匹配通常的定义和计数,
“ N 的整数分区”可以被认为是:
- 正整数元组,按降序排列,总和为 N
- 如果无符号整数向量的元素之和(没有整数溢出)为 N,则它是 N 的“分区”。
我想编写一个函数 f(N,k) ,它随机且均匀地在长度为 k 的可能向量中进行选择,对 N 进行分区并返回所选向量。
如果有一个适用于所有 k>=1 的解决方案,那就太好了,但我对 k > N 特别感兴趣。因此,如果它有助于集中或限制该条件,那就可以了。如果我们必须深入研究近似/启发式方法,则可以考虑 k 足够大,以至于大多数向量条目必须为零(因此至少 k > 2N)。
我最初的想法是:
- 如果 N 足够小,可以合理地计算(或在表中查找?) N 的整数分区数,那么也许我们可以继续:
- 创建一个由 k 个无符号整数组成的向量,初始化为零
- 对 N 进行随机整数分区。令 m 为该元组的长度。
- 将这些值放置在向量的初始 m 个位置。
- 随机打乱向量。
这会天真地认为输出向量中包含 N 的一个条目的可能性与包含 1 的 N 个条目的可能性相同。这是不正确的。但也许有一个简单的权重可以应用于“制作 N 的随机整数分区”,这可以纠正这个问题?
- 另一种方法感觉更干净,但可能仍然需要在某个地方“重新加权”:
- 创建一个由 k 个无符号整数组成的向量,初始化为零
- 执行以下N次:
- 随机选择向量的一个元素并递增它
虽然一开始感觉更干净,但我认为尝试“重新加权”会更加混乱。虽然第 1 部分的权重对我来说听起来像是一个困难的算法问题,但我至少可以想象需要计算什么。在这里,我什至不确定什么需要重新加权以及如何重新加权。
我认为它可能仍然需要重新加权的原因是,恰好有一个随机选择序列会导致向量看起来像 [N,0,0,...,0],并且 N!随机选择序列将导致向量以 N 个 [1,1,...,1,0,0,...,0] 开头。计算最终结果的这些“不正确的权重”的比率听起来是可行的,但我不知道如何重新权衡各个步骤来纠正它。
- 或者也许还有另一种完全是我没有想到的方法?
生成 0-n k-1 次范围内的随机 int。将它们视为 [1, 1, ..., 1] <- 大小 n 的分区。然后分区(和端点)之间的总和就是你的向量。
例如,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]
这是用于此目的的 Ruby 代码:
由于排序,运行时间为 O(k log k)。我们也许可以通过按排序顺序生成随机数来避免排序。
- 更新 -
这并不统一。这是 f(4,2) 的一百万次运行
- - 更新 - -
星星和酒吧都有效。这是 Ruby 代码和另一百万次运行: