random - 随机抽样整数分区（不限制部分数量）

Question

我有一个整数 N，我希望随机生成一个可能的分区。例如，N=5 有 7 个分区：

1. (5) - K=1 份
2. (4, 1) - K=2 份
3. (3, 2) - K=2 份
4. (3, 1, 1) - K=3 份
5. (2, 2, 1) - K=3 份
6. (2, 1, 1, 1) - K=4 份
7. (1, 1, 1, 1, 1) - K=5 份

我想要一种算法，它可以以 1/7 的概率输出这些中的每一个。

生成所有此类分区或仅限于 K 个部分的所有分区的算法很容易找到。

但是，我正在寻找的不是先验限制 K。我不能随机均匀地选择 K，因为 K 不是均匀分布的，而且分布不是微不足道的。如果我事先知道零件尺寸的精确分布，我可以使用它对 K 进行采样，然后使用现有算法之一，但我找不到这样做的方法。一项数值调查表明，绝大多数分区的 K 都很小。

我无法预先生成分区列表，因为 N=100 已经有数亿个分区了。但即使对于我需要的范围内的 N=1000，每个单独的分区也将主要是一个小数字的简短列表。

这样的算法存在吗？我找不到它，我已经找了好几天了。

标签： randominteger-partition