<p>假设需要n_1 in[10,30]、n_2 in[20,40]、n_3 in[30,50]和n1+n2+n3=90</p>
<p>如果你需要每一个可能的三重态(n_1,n_2,n_3)的可能性相等,那就很困难了。形式的三元组(20,nã2,nã3)的数目大于三元组(10,nã2,nã3)的数目,因此不能只均匀地选取nã1。</p>
<p>令人难以置信的缓慢但准确的方法是在正确的范围内生成所有5个随机数,如果总和不正确则拒绝整个组。</p>
<h3>。啊哈!</h3>
<p>我找到了一种有效地参数化选择的方法。不过,首先,为简单起见,请注意下界之和是可能的最小和。如果从目标数中减去下界之和,然后从每个生成的数中减去下界,则会出现一个问题,其中每个数都在区间[0,max_k-min_k]内。这简化了数学和数组(列表)处理。设n_k为基于0的选择,0<;=n_k<;=max_k-min_k</p>
<p>和的顺序是字典式的,所有的和首先以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的数开始计算原始和)。</p>
<p>假设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)的卷积给出了分布。</p>
<p>是时候停止一些代码了:</p>
<pre><code> 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
</code></pre>
<p>这是专门为使用“脉冲”阵列进行卷积而编码的,因此卷积中的每个线性组合只是一个和。</p>
<p>这些只在最终类解决方案的构造函数中使用:</p>
<pre><code>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
</code></pre>
<p>将其用于:</p>
<pre><code>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.
</code></pre>
<p>……等等,这个类可以稍微减少一点,但是主空间开销在rconv列表中,该列表包含存储的卷积。大约是N*T/2,用于O(NT)存储。</p>
<p>卷积只使用范围,在相同的约束条件下产生大量随机数,表的构建时间“摊销”为零。next()的时间复杂度平均约为T/2,而O(T)则是进入rconv列表的索引数。</p>
<hr/>
<p>为了了解算法的工作原理,假设一个序列有3个基于零的选择,最大值(5,7,3)和一个基于0的目标T=10。在空闲会话中定义或导入pulse和stepconv函数,然后:</p>
<pre><code>>>> 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
</code></pre>
<p>K3[i]显示不同选择n_1,n_2,n_3的数目,使得0<;=n_k<;=m_k和∑n_k=i。当应用于其中两个列表时,让*表示卷积。然后脉冲(m_2)*脉冲(m_3)给出n_2和n_3的和的分布:</p>
<pre><code>>>> R23 = stepconv(pulse(7),3)
>>> R23
[1, 2, 3, 4, 4, 4, 4, 4, 3, 2, 1]
>>> len(R23)
11
</code></pre>
<p>从0到T=10的每个值(几乎)都是可能的,所以第一个数字的任何选择都是可能的,并且有R23[T-n_1]个可能的三元组加上以N1开头的T=10。因此,一旦发现有18个可能的和加上10,就生成一个随机数S=randint(18),并通过R23[T:T-m_1-1:-1]数组进行倒计时:</p>
<pre><code>>>> R23[10:10-5-1:-1]
[1, 2, 3, 4, 4, 4]
>>> sum(R23[10:10-5-1:-1])
18
</code></pre>
<p>请注意,该列表的总和是上述K3[10]中计算的总和。健康检查。不管怎样,如果S==9是随机选择,那么求出该数组中可以求和的前导项有多少,而不超过S。这就是n_1的值。在本例中,1+2+3<;=S,但1+2+3+4>;S,所以n_1是3。</p>
<p>如上所述,您可以找到第二个问题。最后的数字(本例中的n_3)将唯一确定。</p>