创建约束随机数？

Question

清除的文本：

如何创建m=5的随机数，将upp相加，比如n=100。但是，第一个随机数是10<；x1<；30，第二个随机nr是5<；x2<；20，第三个随机nr是10<；x3<；25等等，所以这五个随机数加起来就是100。如何创建这些受约束的五个数字？

是的。

[[

相关问题A1）：创建五个加起来等于100的随机数的标准方法是在[0100]之间抽样四个数，并添加边界0和100，然后对这六个数进行排序[0、x1、x2、x3、x4100]。我寻找的五个随机数，是三角。也就是说

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）：创建5个边界为10<；x庘i<；30且相同的的数字的部分解决方案，其总和为100，如下所示：只需在A1）中将下边界10添加到delta。所以我得到五个随机数，我寻找如下：

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？这里的问题是如何限制上边界

]]

是的。

概括地说，我试图解决的问题的类型如下：我需要5个随机数，加起来是100，我需要分别为每个数指定边界，比如第一个随机数为[10,30]，第二个随机数为[5,10]，第三个随机数为[15,35]，等等，它们加起来必须是100。

但我使用的真实数据，有大约100个数字xòI（m=50），所有这些加起来就是大约40万。对于一个数字x}i，这个范围通常是[30005000]，这些数字并不是很准确，我只是想传达一些关于问题大小的信息。目的是做一个MCMC模拟，所以这些数字需要快速生成。人们已经提出了非常优雅的解决方案，这些方案确实有效，但它们花费的时间太长，所以我不能使用它们。这个问题还没有解决。理想情况下，我想要一个O（m）解决方案和O（1）内存解决方案。

这个问题不应该是NP难的，它感觉不像。应该有多项式时间解，对吧？

Answer 1

试试这个：

import random
a = random.randint(10, 30)
b = random.randint(5, 20)
c = random.randint(10, 25)
d = random.randint(5, 15)
e = 100 - (a+b+c+d)

编辑：

下面是如何生成给定n范围约束和所需目标和的n随机数的列表：

def generate(constraints, limit):
    ans = [random.choice(c) for c in constraints]
    return ans if sum(ans) == limit else generate(constraints, limit)

这就是你使用它的方法：

generate([range(10,31),range(5,21),range(10,26),range(5,16),range(10,26)], 100)
=> [25, 20, 25, 12, 18]

不过，请注意：如果约束不能保证最终达到总和，则会出现无限循环和堆栈溢出错误，例如：

generate([range(1,11), range(10, 21)], 100)
=> RuntimeError: maximum recursion depth exceeded while calling a Python object

Answer 2

首先，定义范围：

ranges = [range(11,30), range(6,20), range(11,25)]

然后列举所有可能性：

def constrainedRandoms(ranges):
    answer = []
    for vector in itertools.product(*ranges):
        if sum(ranges) == 100:
            answer.append(vector)
    return answer

等效一层：

answer = [v for v in itertools.product(*ranges) if sum(v)==100]

然后从中选择一个随机元素：

myChoice = random.choice(answer)

编辑：

笛卡尔积（用itertools.product计算）本身不占用太多RAM（这是因为itertools.product返回一个生成器，它使用O（1）空间，但正如您所指出的，它占用了很多时间）。只有计算列表（answer）才可以。坏消息是，为了使用random.choice，您需要一个列表。如果你真的不想使用列表，那么你可能需要提出一个衰减概率函数。下面是一个非常简单的概率函数，您可以使用它：

def constrainedRandoms(ranges):
    choices = (v for v in itertools.product(*ranges) if sum(v)==100) # note the parentheses. This is now a generator as well

    prob = 0.5
    decayFactor = 0.97 # set this parameter yourself, to better suit your needs
    try:
        answer = next(choices)
    except StopIteration:
        answer = None
    for choice in choices:
        answer = choice
        if random.uniform(0,1) >= prob:
            return answer
        prob *= decayFactor
    return answer

衰减概率允许您增加选择符合约束的下一个向量的概率。这样想：你有很多限制。很可能，会有相对较少的向量满足这些约束。这意味着每次你决定不使用一个向量时，有另一个这样的向量的概率就会降低。因此，随着时间的推移，您需要逐渐地更偏向于将当前向量返回为“随机选择的向量”。当然，仍然可以遍历整个循环结构而不返回向量。这就是为什么代码从符合约束条件的第一个向量的默认值开始（假设存在约束条件），如果衰减概率不允许返回向量，则返回最后一个向量。
注意，这种衰减概率思想允许您不必迭代所有候选向量。随着时间的推移，代码返回所考虑的当前向量的概率增加，从而降低了代码继续并考虑其他向量的概率。因此，这个想法也有助于减轻您对运行时的担忧（不过，我很不好意思补充，不是很担心）

Answer 3

假设需要n_1 in[10,30]、n_2 in[20,40]、n_3 in[30,50]和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的选择，0<；=n_k<；=max_k-min_k

和的顺序是字典式的，所有的和首先以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个1的列表：（n+1）*[1]，用Python术语来说。设max_k，min_k为第k个选择的限制，m_k=max_k-min_k为基于0的选择的上限。然后有1+mç1不同的“和”从第一个数的选择，并且脉冲（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列表中，该列表包含存储的卷积。大约是N*T/2，用于O（NT）存储。

卷积只使用范围，在相同的约束条件下产生大量随机数，表的构建时间“摊销”为零。next（）的时间复杂度平均约为T/2，而O（T）则是进入rconv列表的索引数。

---

为了了解算法的工作原理，假设一个序列有3个基于零的选择，最大值（5,7,3）和一个基于0的目标T=10。在空闲会话中定义或导入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。当应用于其中两个列表时，让*表示卷积。然后脉冲（m_2）*脉冲（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的每个值（几乎）都是可能的，所以第一个数字的任何选择都是可能的，并且有R23[T-n_1]个可能的三元组加上以N1开头的T=10。因此，一旦发现有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_3）将唯一确定。