如何生成统一的随机整数分区？
Google搜索显示了很多关于生成整数n到m个部分的所有可能分区的信息,但我还没有找到任何关于将n均匀分布的随机分区采样为m个部分的信息.
Ste*_*lvo 13
这篇文章的标题有点误导.默认情况下,随机整数分区不受限制,这意味着它可以包含任意大小的任意数量的部分.提出的具体问题是将n分区为m个部分,这是一种受限制的整数分区.
为了生成不受限制的整数分区,在一篇名为"大整数随机分区的结构"(1993)的论文中,Fristedt提出了一种非常快速和简单的算法.算法如下:
- 设置x = exp(-pi/sqrt(6n)).
- 生成独立的随机变量Z(1),Z(2),...,Z(n),其中Z(i)在几何上分布有参数1-x ^ i.
- IF sum i*Z(i)= n,其中总和取自所有i = 1,2,...,n,然后是STOP.
ELSE,重复2.
一旦算法停止,则Z(1)是1的数量,Z(2)是在随机均匀选择的分区中的2的数量等.接受随机选择的Z集合的概率渐近1 /(94n ^ 3)^(1/4),这意味着在接受单个算法之前,人们期望运行该算法O(n ^(3/4))次.样品.
我花时间解释这个算法的原因是因为它直接适用于将n的分区生成为m个部分的问题.首先,观察一下
n到m个部分的分区数等于n的分区数,最大部分等于m.
然后我们可以直接应用Fristedt算法,但不是生成Z(1),Z(2),...,Z(n),我们可以生成Z(1),Z(2),...,Z( m-1),Z(m)+1(此处的+1确保最大部分正好为m,并且1 + Z(m)在Z(m)> = 1的条件下与Z(m)的分布相等并设置所有其他Z(m + 1),Z(m + 2),...等于0.然后,一旦我们在步骤3中获得目标总和,我们也保证有一个无偏的样本.为了将n的分区精确地分成m个部分,只需获取所生成的分区的共轭.
这对于Nijenhuis和Wilf的递归方法的优点是除了存储随机变量Z(1),Z(2)等之外没有存储器要求.此外,x的值可以是0到0之间的任何值. 1,这个算法仍然没有偏见!然而,选择良好的x值可以使算法更快,尽管步骤1中的选择对于不受限制的整数分区几乎是最佳的.
如果n非常大并且Fristedt的算法花费的时间太长(并且表格方法是不可能的),那么还有其他选择,但它们有点复杂; 有关概率分而治之及其应用的更多信息,请参阅我的论文https://sites.google.com/site/stephendesalvo/home/papers.
- 集合分区是一个程序集的示例：https://arxiv.org/pdf/1308.3279.pdf 使用 Poisson(\lambda_i) 代替 Geometric，其中 \lambda_i = x^i/i!，对于任何 x >0 ，其中 x 满足： x*e^x = n 是最优的。使用 PDC 确定性后半部分的极快算法出现在：https://arxiv.org/pdf/1411.6698.pdf 第 8.7 节 (2认同)
Jas*_*rff 10
这是一些代码.这是第一次调用时的O(n 2),但它会构建一个缓存,以便后续调用为O(n).
import random
cache = {}
def count_partitions(n, limit):
if n == 0:
return 1
if (n, limit) in cache:
return cache[n, limit]
x = cache[n, limit] = sum(count_partitions(n-k, k) for k in range(1, min(limit, n) + 1))
return x
def random_partition(n):
a = []
limit = n
total = count_partitions(n, limit)
which = random.randrange(total)
while n:
for k in range(1, min(limit, n) + 1):
count = count_partitions(n-k, k)
if which < count:
break
which -= count
a.append(k)
limit = k
n -= k
return a
这是如何工作的:我们可以计算O(n 2)时间内整数n的分区数.作为副作用,这产生一个大小为O(n 2)的表,然后我们可以使用它来在O(n)时间内为任何整数k生成n的第k个分区.
所以让total =分区数.从0到总数中选择一个随机数k - 1.生成第k个分区.
另一种算法来自组合算法第 52 页，“随机生成n零件k”
- 选择
a1,a2, .. 的ak-1随机k-1子集{1,2,..,n+k-1}（见下文 1., 2.） - 放 ; ( );
r1=a1-1rj=aj-aj-1-1j=2..k-1rk= n+k-1-ak-1 - ( )构成
rj的随机划分j=1..knk
这种随机组合的算法基于“细胞中的球”模型。
简而言之，我们随机选择单元边界的位置，然后通过差分找出每个单元中有多少个球。
为了有效地生成集合的随机子集，请参阅此处的 1.相关答案和此处的2.相关答案
更新
IVAN STOJMENOVIC，“组合对象的随机和自适应并行生成”（第 5 节，第 10 节）[0,1]中给出了另一种使用单个随机数来统一生成随机分区（也称为组合）的方法
