如何生成一个统一的随机整数分区? [英] How do I generate a uniform random integer partition?
问题描述
有一个谷歌搜索发现大量有关生成的整数n成m部分所有可能的分区,但我还没有发现有关抽样n的均匀分布的随机划分成m部分东西。
A Google search reveals plenty about generating all possible partitions of an integer n into m parts, but I haven't found anything about sampling a uniformly distributed random partition of n into m parts.
推荐答案
下面是一些code,做它。这是O( N 的 2 )的第一次调用它,但它构建了一个高速缓存,以使后续调用是O( N 的)。
Here is some code that does it. This is O(n2) the first time you call it, but it builds a cache so that subsequent calls are 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
如何工作的:我们可以计算出一个整数的多个分区的 N 的还有在O( N 的 2 )的时间。作为一个副作用,这产生的O号的表( N 的 2 ),我们就可以用它来生成 K 个分区 N 的,对于任何整数的 K 的,在O( N 的)时间。
How this works: We can calculate how many partitions of an integer n there are in O(n2) time. As a side effect, this produces a table of size O(n2) which we can then use to generate the kth partition of n, for any integer k, in O(n) time.
因此,让我们的总的=分区的数量。从0选择一个随机数的 K 的到的总的 - 1.生成的 K 个分区
So let total = the number of partitions. Pick a random number k from 0 to total - 1. Generate the kth partition.
这篇关于如何生成一个统一的随机整数分区?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!