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

在Python中随机生成特定长度的整数分区的算法?,第1张

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

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

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(https://stackoverflow.com/users/494076/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


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5663995.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表(0条)

保存