在Python中随机生成特定长度的整数分区的算法？

小编典典

在Python中随机生成特定长度的整数分区的算法？

python

我一直在使用random_element()SAGE提供的函数为给定整数（N）生成随机整数分区，该整数是特定长度（S）。我正在尝试根据给定的N和值，从所有分区的集合中生成无偏随机样本S。SAGE的函数快速返回N的随机分区（即Partitions(N).random_element()）。

但是，添加时S（即Partitions(N,length=S).random_element()）会极大地减慢速度。同样，过滤掉N长度一定的随机分区S非常慢。

但是，我希望这对某人有帮助，我发现在函数返回N不匹配length的分区的情况下S，共轭分区的长度通常为S。即：

S = 10
N = 100
part = list(Partitions(N).random_element())
    if len(part) != S:
        SAD = list(Partition(part).conjugate())
        if len(SAD) != S:
            continue

这会增加S找到长度分区的速度，并且似乎会产生无偏样本（我已经针对N和的各种值针对整个分区集检查了结果S）。

但是，我使用的N值（例如10,000）和S值（例如300）会使这种方法变得不切实际地缓慢。与SAGErandom_element()功能相关的注释承认有足够的优化空间。因此，是否有一种方法可以更快地生成与给定值N和相匹配的整数分区的无偏（即随机均匀）样本S，也许不生成不匹配的分区S？此外，使用共轭分区在许多情况下都能很好地生成无偏样本，但是我不能说我完全理解为什么。

阅读 225

2021-01-20

共1个答案

小编典典

最后，我有一个绝对无偏的方法，其拒绝率为零。当然，我已经对其进行了测试，以确保结果是整个可行集的代表样本。它的速度非常快，完全没有偏见。请享用。

from sage.all import *
import random

首先，该函数查找具有s个部分的n分区的最小最大加数

def min_max(n,s):

    _min = int(floor(float(n)/float(s)))
    if int(n%s) > 0:
        _min +=1

    return _min

接下来，该函数使用缓存和记忆来查找n个分区的数量，其中s个部分以x为最大部分。
这很快，但是我认为还有一个更优雅的解决方案。例如，通常：P（N，S，max = K）=
P（NK，S-1）感谢ante为我提供了帮助：查找数字给定总数，部分数量和最大和的整数分区的数量

D = {}
def P(n,s,x):
    if n > s*x or x <= 0: return 0
    if n == s*x: return 1
    if (n,s,x) not in D:
        D[(n,s,x)] = sum(P(n-i*x, s-i, x-1) for i in xrange(s))
    return D[(n,s,x)]

最后，一个函数可以找到n个具有s个部分的均匀随机分区，并且没有拒绝率！每个随机选择的数字编码用于n个具有s部分的特定分区。

def random_partition(n,s):
    S = s
    partition = []
    _min = min_max(n,S)
    _max = n-S+1

    total = number_of_partitions(n,S)
    which = random.randrange(1,total+1) # random number

    while n:
        for k in range(_min,_max+1):
            count = P(n,S,k)
            if count >= which:
                count = P(n,S,k-1)
                break

        partition.append(k)
        n -= k
        if n == 0: break
        S -= 1
        which -= count
        _min = min_max(n,S)
        _max = k

    return partition

2021-01-20