python - 创建受约束的随机数？

Question

清理文本:

我如何创建m = 5个将upp加到上的随机数，例如n = 100。但是，第一个随机数是10
。

[[

相关问题A1):创建五个加起来为100的随机数的标准方法是对[0,100]之间的四个数字进行采样，并添加边界0和100，然后对这六个数字[0，x1，x2， x3，x4,100]。我寻找的五个随机数是增量。那是，

100 - x[4] = delta 5
x[4]- x[3] = delta 4
x[3]- x[2] = delta 3
x[2]- x[1] = delta 2
x[1] - 0   = delta 1

这五个增量现在总计为100。例如，它们可能为0、1、2、7、90。这是一些解决此问题的代码:

total_sum = 100
n = 5
v = numpy.random.multinomial(total_sum, numpy.ones(n)/n)

]]

。

对于我的问题，我不允许出现较大的时间间隔，上方的最大价差是90-7 = 83，这太宽了。因此，我必须指定更紧密的利差，例如[10,30]。这意味着最大的随机数是30，不允许出现较大的点差，例如83。

。

[[

相关问题A2):创建具有五个相同边界(10

100 - x[4] = delta 5 + 10
x[4]- x[3] = delta 4 + 10
x[3]- x[2] = delta 3 + 10
x[2]- x[1] = delta 2 + 10
x[1] - 0   = delta 1 + 10

基本上，我确实像A1)中一样，但不是从0开始，而是从10开始。因此，每个数字的下边界为10，但它们没有上限，它可能很大，也可能太大。如何将上限限制为30？这里的问题是如何限制上限

]]

。

概括地说，我尝试解决的问题的类型如下所示:我需要五个随机数加起来等于100，并且需要分别为每个数字指定边界，例如，第一个随机数为[10,30]，并且然后，[5,10]代表第二个随机数，[15,35]代表第三个随机数，依此类推。它们必须加起来等于100。

但是我使用的真实数据有〜100个数字x_i(m = 50)，所有这些数字加起来约为40万。对于数字x_i，范围通常为[3000,5000]。这些数字不是很准确，我只是想传达一些有关问题大小的信息。目的是进行MCMC仿真，因此需要快速生成这些数字。人们提出了非常实用的非常优雅的解决方案，但是它们花费的时间太长，因此我无法使用它们。该问题仍未解决。理想情况下，我需要O(m)解决方案和O(1)内存解决方案。

这个问题不应该是NP难题，它不像它。应该有一个多项式时间解，对吗？

Answer 1

假设您需要[10,30]中的n_1，[20,40]中的n_2，[30,50]中的n_3以及n1 + n2 + n3 = 90
如果您需要每个可能的三元组(n_1，n_2，n_3)都一样，那将很困难。形式(20，n_2，n_3)的三元组的数量大于(10，n_2，n_3)的三元组的数量，因此您不能只是均匀地选择n_1。
令人难以置信的缓慢但准确的方法是在正确的范围内生成所有5个随机数，如果总和不正确，则拒绝整个组。
。 。 。啊!
我找到了一种有效地参数化选择的方法。首先，为简单起见，请注意，下限之和是最小可能的总和。如果从目标数字中减去下限的总和，然后从每个生成的数字中减去下限，则会出现一个问题，其中每个数字的间隔为[0，max_k-min_k]。这简化了数学和数组(列表)处理。令n_k为0 <= n_k <= max_k-min_k的从0开始的选择。
总和的顺序是按字典顺序，所有总和首先以n_1 = 0(如果有)开头，然后是n_1 == 1总和，依此类推。总和在每个组中按n_2排序，然后按n_3排序，依此类推。如果您知道有多少个和添加到目标(称为T)，以及有多少个以n_1 = 0,1,2，...开头，那么您可以在该列表中找到总和S的起始数字n1。然后，您可以减少问题，将n_2 + n_3 + ...添加到T-n_1，找到总和S-(原始总和的数量以小于n_1的数量开始)。
令pulse(n)为n + 1个的列表:(n + 1)* [1]用Python术语表示。令max_k，min_k为第k个选择的极限，m_k = max_k-min_k为基于0的选择的上限。那么从第一个数字的选择中就有1 + m_1个不同的“和”，而pulse(m_k)给出了分布:1是使每个和从0到m_1。对于前两个选择，有m_1 + m_ + 1个不同的和。事实证明，脉冲(m_1)与脉冲(m_2)的卷积给出了分布。
是时候停止一些代码了:

    def pulse(width, value=1):
        ''' Returns a vector of (width+1) integer ones. '''
        return (width+1)*[value]

    def stepconv(vector, width):
        ''' Computes the discrete convolution of vector with a "unit"
            pulse of given width.

            Formula: result[i] = Sum[j=0 to width] 1*vector[i-j]
            Where 0 <= i <= len(vector)+width-1, and the "1*" is the value
            of the implied unit pulse function: pulse[j] = 1 for 0<=j<=width.
        '''
        result = width*[0] + vector;
        for i in range(len(vector)):
            result[i] = sum(result[i:i+width+1])
        for i in range(len(vector), len(result)):
            result[i] = sum(result[i:])
        return result

这是专门为仅使用“脉冲”数组进行卷积而编码的，因此卷积中的每个线性组合都是和。
这些仅在最终类解决方案的构造函数中使用:

class ConstrainedRandom(object):
    def __init__(self, ranges=None, target=None, seed=None):
        self._rand = random.Random(seed)
        if ranges != None: self.setrange(ranges)
        if target != None: self.settarget(target)

    def setrange(self, ranges):
        self._ranges = ranges
        self._nranges = len(self._ranges)
        self._nmin, self._nmax = zip(*self._ranges)
        self._minsum = sum(self._nmin)
        self._maxsum = sum(self._nmax)
        self._zmax = [y-x for x,y in self._ranges]
        self._rconv = self._nranges * [None]
        self._rconv[-1] = pulse(self._zmax[-1])
        for k in range(self._nranges-1, 0, -1):
            self._rconv[k-1] = stepconv(self._rconv[k], self._zmax[k-1])

    def settarget(self, target):
        self._target = target

    def next(self, target=None):
        k = target if target != None else self._target
        k = k - self._minsum;
        N = self._rconv[0][k]
        seq = self._rand.randint(0,N-1)
        result = self._nranges*[0]
        for i in range(len(result)-1):
            cv = self._rconv[i+1]
            r_i = 0
            while k >= len(cv):
                r_i += 1
                k -= 1
            while cv[k] <= seq:
                seq -= cv[k]
                r_i += 1
                k -= 1
            result[i] = r_i
        result[-1] = k # t
        return [x+y for x,y in zip(result, self._nmin)]
    
    # end clss ConstrainedRandom

结合使用:

ranges = [(low, high), (low, high), ...]
cr = ConstrainedRandom(ranges, target)
seq = cr.next();
print(seq)
assert sum(seq)==target

seq = cr.next(); # get then get the next one.

...等等。该类可以减少一些，但是主要的空间开销在_rconv列表中，该列表具有存储的卷积。对于O(NT)存储，大约为N * T/2。
卷积仅使用范围，并且在相同约束条件下生成大量随机数，表构建时间“摊销”为零。就_rconv列表中的索引数而言，.next()的时间复杂度平均约为T/2，O(T)。

要了解该算法的工作原理，请假设一个包含3个从零开始的选择的序列，最大值为(5,7,3)，从0开始的目标值为T = 10。在一个空闲 session 中定义或导入Pulse和stepconv函数，然后:

>>> pulse(5)
[1, 1, 1, 1, 1, 1]
>>> K1 = pulse (5)
>>> K2 = stepconv(K1, 7)
>>> K3 = stepconv(K2, 3)
>>> K1
[1, 1, 1, 1, 1, 1]
>>> K2
[1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1]
>>> K3
[1, 3, 6, 10, 14, 18, 21, 23, 23, 21, 18, 14, 10, 6, 3, 1]
>>> K3[10]
18
>>> sum(K3)
192
>>> (5+1)*(7+1)*(3+1)
192

K3 [i]显示不同选择n_1，n_2，n_3的数量，以使0 <= n_k <= m_k和Σn_k = i。当将*应用于其中两个列表时，表示*为卷积。然后，pulse(m_2)* pulse(m_3)给出n_2和n_3之和的分布:

>>> R23 = stepconv(pulse(7),3)
>>> R23
[1, 2, 3, 4, 4, 4, 4, 4, 3, 2, 1]
>>> len(R23)
11

从0到T = 10的每个值都是(几乎)是可能的，因此第一个数字的任何选择都是可能的，并且以N1开头的T = 10中有R23 [T-n_1]个可能的三元组。因此，一旦发现有18种可能的总和加到10，就生成一个随机数S = randint(18)并通过R23 [T:T-m_1-1:-1]数组递减计数:

>>> R23[10:10-5-1:-1]
[1, 2, 3, 4, 4, 4]
>>> sum(R23[10:10-5-1:-1])
18

请注意，该列表的总和是上述K3 [10]中计算出的总和。健全性检查。无论如何，如果S == 9是随机选择，则找出不加S的情况下可以求和该数组的多少个前导项。这就是n_1的值。在这种情况下1 + 2 + 3 <= S但1 + 2 + 3 + 4> S，所以n_1为3。
如上所述，您可以减少问题来查找n_2。最终编号(在此示例中为n_3)将唯一确定。