创建受约束的随机数？

Question

清理文字:

如何创建添加upp的m = 5个随机数,比如n = 100.但是,第一个随机数是10 <x1 <30,第二个随机nr是5 <x2 <20,第三个随机nr是10 <x3 <25,等等.所以这五个随机数加起来为100.我可以创建这些约束的五个数字吗？

.

[[

相关问题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 个数字的部分解决方案,10 <x_i <30,加起来为100就像这样:只是在A1中做,但是将下边界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),所有这些数据总计大约400,000.对于数字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 的选择，其中 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 的列表：(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 个不同的和。事实证明，pulse(m_1) 与pulse(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。在空闲会话中定义或导入脉冲和 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 的每个值都是（几乎）可能的，因此第一个数字的任何选择都是可能的，并且有 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_2。最终数字（在本例中为 n_3）将被唯一确定。