如何把一个数字 x 随机分成 y 个数字，这些数字≥a 且≤b

[kaiki]

类似发红包的算法，但是加了个最大值和最小值限制，自己写了一个感觉不太行，有没有简单的办法？

[windmelon]

想到的简单的方法，但是不知道对随机性有多大影响
即按照每次从[a,b]区间取数的方法每次取一个数，取 Y 次
只不过多一步判断，所取区间的下限是否满足剩余的数都取 b 满足和大于等于 X，否则就提高区间下限[a+,b]

[Dvel]

一个简单的思路：
x=100 块钱，y=10 个人，a=最小 5，b=最大 15 。
那么第 1 次分配：剩余金额需要满足 5*10 <= 100 <= 15*10 的范围。
那么第 2 次分配：剩余金额需要满足 5*9 <= 剩余金钱 <= 15*9 的范围。
...
...
那么第 9 次分配：剩余金额需要满足 5*2 <= 剩余金钱 <= 15*2 的范围。
那么第 10 次分配：剩余金额需要满足 5 <= 剩余金钱 <= 15 的范围。

就是每次分配完，判断剩余金额是否在合理范围内，在就继续，不在就重新分配。

```
from random import randint


def hongbao(x, y, a, b):
result = []
for i in range(y):
result.append(randint(a, b))
while x - sum(result) > b * (y - i - 1) or x - sum(result) < a * (y - i - 1):
result[i] = randint(a, b)
return result


r = hongbao(100, 10, 5, 15)
print(r, sum(r))
```

优化的时候加一个最后一次直接求结果就行。

[FFFire]

@Sapp 但这样最后的结果还是可能会超出[a,b]区间

[chengfeng1992]

https://gist.github.com/chengfeng-1992/1ab94bfdab77d395a0dd87b6feb51974

@kaiki @sillydaddy 在#7 想法的基础上，多加了一句判断，测试了下没大问题。

[sillydaddy]

@chengfeng1992
我前面说的主要不是最后一个值越界的问题，而是结果不随机的问题。
你可以运行一下自己的程序，多次运行以后，计算出各个人得到的红包平均数，看是不是相等的。如果不相等说明红包算法随机性有问题。

我可以举个肉眼可见的例子，
x=11，y=3，a=1，b=5，意思就是 11 元红包分给 3 个人，最小 1 元，最大 5 元。
简单看一下 3 个人分得的红包分布
1，5，5
2，4.5，4.5
3，4，4
4，3.5，3.5
5，3，3
可以看出来，后面抽红包的两个人，他们的平均期望值是 4，而第一个人的期望只有 3 。
这说明这种算法不是均匀随机的。

[everhythm]

有一个比较简单的预分配的方法：


1. 数字 x 平均分成 y 份

2. random 1 个差值，从 y 份中取出 2 个数，第 1 个加上这个差值，第 2 个减去这个差值，得到的 2 个结果如果满足 >=a 且 <=b，就相当于随机分配了 2 个数字。一直循环到分配完成。

3. 可以 random 多个差值，附加到 y 份中多份数字上

[BiteTheDust]

可以先随便分 最后对分好的做一个随机排列 这样期望就是相等的了

[chengfeng1992]

@sillydaddy #25 试了几组数据，对于某些数据结果数据较为均匀，对于某些数据有较明显的升序或降序特征。说明这确实不是一个好算法。
如果把最终结果再随机排列一次，这种“亡羊补牢”式的做法可取吗？

[h272377502]

先在每个红包里先放 a 。剩余量（ R ）：x-ya 。每个红包的剩余容量（ C1,C2,C3...）：b-a 。

选择一个数字 k （见脚注如何选择 k ）。如果它大于 R，那么将它设为 R (k=min(k,R) )。随机选取一个红包 i 。如果 Ci 小于 k，则 k 设为 Ci ( k=min(k,Ci) )。现在将 k 部分钱放入红包 i 中，更新 R 和 Ci （ R=R-k，Ci=Ci-k ）。重复这个过程，直到所有的红包都被分完（ R=0 ）。

脚注：挑选 k 个

你可以设置 k=1 或从任何适当的分布中选择 k （例如：从 1 到 10 中随机选择 k ）。

import random
def distPotato(R, N, minP, maxP):
C = [maxP-minP for i in range(N)]
V = [minP for i in range(N)]
R-=sum(V)
while(R>0):
k = random.uniform(0, 10)
i = random.choice(range(N))
k = min(k,R)
k = min(k, C[i])
C[i]-=k
R-=k
V[i]+=k
return V

v = distPotato(100.5,3,15.2,60.3)

可参考原答案（离散和连续应该是一样的道理）： https://stackoverflow.com/questions/10561804/randomly-put-elements-into-n-buckets/10561932

[JeffGe]

@Dvel 我想了好久，你这个算法严格来说分布不均匀吧。如果严格均匀，那么意味着 10 个随机变量 X1 ~ X10 是轮换对称的对吧，而且这 10 个随机变量应该是同分布的。你这算法第一个随机变量（在合适的参数下）一定是均匀分布的，可他们应该不是同均匀分布的随机变量啊

[Dvel]

@JeffGe #30 呃我算法渣，没看懂你说的。。。
我试了一下运行 100 万次，然后取每个人的平均数是：
10.00439
10.002429
9.999853
9.998824
9.999526
9.999866
9.996083
10.003026
9.997349
9.998654

[Enix]

把很久以前做过的类似的凭印象写了一遍，思路是根据权重分配剩余值（ x - y * a ），大致代码

[Enix]

注释一下——
flatten weights 处借助了 `Math.random()` 值域为 0-1 的特点，令 weights 的最值之差减小

`weight * weight` 也许可以改为 `Math.sqrt(weight)` 或其他运算，获得更好的平权效果，没细想

[JeffGe]

@Dvel 不是，这不是算法问题，你的算法我认为是一个应对发红包这样一个应用来说挺好的，效率也不错的一个算法。我只是在描述一个数学问题，就像 @sillydaddy 在 8 楼所说的，这是一个在 (n-1) 维的多边形内部随机取一个点的问题，这个多边形投影到一个轴上的函数就是对应随机变量的概率密度分布函数，我觉得这个函数很大可能不是均匀分布函数。你用蒙特卡洛法得到均值为 10 说明不了什么，你应该把累积概率密度图画出来比较一下。

换个实际的例子理解一下，把你的参数微调一下：a=5, b=11，那么如果完全随机的话，是不是按理说 5 的概率较低，10 或 11 的概率要高得多？但是你的算法在第一步给出 X1 随机变量是 [5, 11] 内均匀分布的。

[fbxshit]

想了个算法不知道够不够随机：
首先 y 个人随机分配共 x 元，分配完成之后把 y 个人按照财富多少从小到大排列。
最穷的那个人的钱是不是小于 a ？或者最富的那个人的钱是不是大于 b ？如果符合以上条件，把最穷的人和最富的人拉出来，数一下他们的财富相差多少钱，在这个财富差距的数值里面随机取一个数字，让最富的人按照这个数字掏出来把钱补贴给最穷的人，补贴完之后把他们两放回到队伍里，这个时候重新按照财富大小给 y 个人排队，这次最穷的人应该比第一次排序时富了一点，最富的人应该比第一次排序时穷了一点。

不断重复以上步骤，直到最穷的人财富大于等于 a，最富的人财富小于等于 b 。

[msg7086]

先按照给定范围随机取值，取完求和然后二分法等比例带上下限浮动。也就是说比如 10 个人 100 块钱算完是 90 块，可以先每个人上涨 10%，然后约束上限，然后看看还差多少。然后再多涨一点，直到超过 100 块。接下来就是二分法在不到 100 块和超过 100 块之间找一个接近的涨幅即可。精度可以拉到一毛钱，最终误差就加给最高或最低的人即可。

[cassyfar]

这个需求本生就没法随机。因为有 a，b 限制。比如 x = 10 和 y = 5 的情况下 b = 2，a = 1，那不是只可能有唯一解了，怎么随机呢？

[sillydaddy]

@chengfeng1992，#28，采样不均匀的话，把结果重排还是不均匀吧。


@cassyfar，#37，最小值最大值只是一个约束吧，并不一定要求一定要取到最小或最大值。

[sillydaddy]

@kaiki
@chengfeng1992
@XiaoxiaoPu
@JeffGe
@fbxshit

想了一下，找到了一个我认为正确的方法。
但基本原理很简单，就是类似前面提到的，在多边形内随机采样取点。

先看一下为什么发红包跟多边形取点会关联起来，举例来说，发红包的条件可以表示为：
x+y+z=11，(给 3 个人发 11 元红包)
x>=2, x<=8， y>=2, y<=8， z>=2, z<=8，
(给每个人发的红包在 2 和 8 之间)

用几何的观点来看，这几个条件表示的是，使用一个立方体(x,y, z 的范围都在 2 ～ 8 之间)，去截取一个平面，平面的方程为 x+y+z=11 。平面被立方体截取的部分(在立方体内的)，就是满足题目要求的解。然后求一个随机解就变成了在被截取的平面上随机采样采点。

如果把这个图形画出来，会发现平面被立方体所截得的图形是一个等边三角形。三个顶点分别是(2,2,7)，(2,7,2)，(7,2,2)

所以，现在的问题变成了：已知一个三角形(凸多边形)，怎么才能做到均匀采样其内部的点？
这个就要感谢凸集的美好性质了：凸集内部的任何一点都可以唯一表示成凸集顶点的线性组合。
假设三角形的三个顶点分别是 P0, P1, P2，那么三角形内部的任一点，可以唯一表示为 a*P0+b*P1+c*P2，其中 a+b+c=1 。
所以要想随机采样三角形内部的点，只要随机取 a,b,c 这三个数，保证和为 1 即可。

上面是 3 维的简单情形，如果发红包给更多的人，就变成了更高维的，但原理是一样的。原来的平面变成了高维平面，原来的立方体变成了高维立方体。关键是求出立方体在平面上截得的顶点。找到所有的顶点后，对这些顶点线性组合就 ok 了。