这是一个创建于 1391 天前的主题，其中的信息可能已经有所发展或是发生改变。
类似发红包的算法，但是加了个最大值和最小值限制，自己写了一个感觉不太行，有没有简单的办法？
 |
1
kiracyan 2021-01-18 14:35:49 +08:00
这样？
for(i= 0;i<y;i++){ var num = random(a,b) x -= num } |
 |
2
Glauben 2021-01-18 14:36:48 +08:00
直接生成[a,b]之间的随机数，从 X 中里扣除，循环 Y 次，最后一次直接用剩下的
|
 |
3
kaiki OP  1
@2435043xia 如果每次随机到的数值都＜(a+b)/2，剩下的就绝对超过 b 了啊
|
 |
4
sillydaddy 2021-01-18 14:39:52 +08:00 via Android
在 0 ～ x 范围内，取 y-1 个随机数，将 x 划分成 y 段，从中取出一段，该段长度符合大于等于 0 小于等于 d ；
从 x 中减去已经取的段，迭代上面的过程，每次迭代时分段数目要减 1 。 把 a ～ b 的范围，转换成上面算法要求的 0 ～ d 即可。 |
|
5
kaiki OP @kiracyan 要分完，我应该直接把数字带入的，x=100，y=10，a=5，b=15
这也随机取到 9 个 5，最后一个岂不是 55 了，大于 15 了 |
|
6
sillydaddy 2021-01-18 14:43:10 +08:00 via Android
@sillydaddy 我说的好像有问题。。不能保证所有段的和等于总和
|
 |
7
chengfeng1992 2021-01-18 14:50:30 +08:00
首先判断 ( x >= a*y ) && (x <= b*y) 来确定有解
然后给每个值分最小值之后的余数 remainder = x - a*y 再然后把余数随机分成 y 份，其中最大值 max = b - a，最小值 min = 0，相当于把问题转化成了简单的红包算法 最后把分成的值分别+a 得到结果 |
|
8
sillydaddy 2021-01-18 14:55:28 +08:00 via Android
想了下，感觉这道题目应该叫，"约束空间范围的随机采样"，就类似于要求在一个多边形内部，随机取一个点。
坐等高手。 |
 |
9
XiaoxiaoPu 2021-01-18 14:58:09 +08:00
设第一个数字使 r1
1. 显然第一个数需要满足 a <= r1<= b 2. 为了使后面的分配仍能继续，需要满足 x - r1 >= (y-1) * a，x - r1 <= (y-1) * b，即 r1 >= x - (y - 1) * a，r1 <= x - (y - 1) * b 综合 1,2 得到 r1 的取值区间 [max(a, x - (y - 1) * a), min(b, x - (y - 1) * b)]（如果无法得到此区间，说明问题无解），在此区间内随机取一个数，即得 r1 。 对于第二个数，转化为数字 x - r1 分成 y - 1 个数字，这些数字≥a 且≤b，同上可得 r2 |
|
10
sillydaddy 2021-01-18 14:59:36 +08:00 via Android
@chengfeng1992 取 max 的过程有点问题吧，感觉这样的话算法不是随机的了。类比我上面举的例子，给定一个 2d 上的多边形，要求在内部随机取点。这时如果先随机取 x，再根据 x 的值，在 x 对应的 y 范围内随机取 y，会导致结果不随机。
|
 |
11
chenluo0429 2021-01-18 15:04:00 +08:00 via Android
你可以先想象一下，先给 y 个数字位置都分配 a，那么问题就变成了把数字(x -ya)随机分成 y 个数字，且这些数字满足[0, b - a]。
|
 |
12
Stoulla 2021-01-18 15:04:14 +08:00 via Android
同意楼上的，或者你可以通过归一化的思想，将[a,b]归一化为［ 0,x]区间，剩下的就是简单的红包问题了
|
|
13
kiracyan 2021-01-18 15:12:21 +08:00
@kaiki 纯随机肯定会出现你说的这种情况的
我的理解是从业务的角度去处理这个问题 Random(a,b) 就会出现 不够分或者分多的情况 Random(a,x) 超过最大值的当 b 就会出现 前面分的多 后面分的少的情况 |
|
14
sillydaddy 2021-01-18 15:15:14 +08:00 via Android 1
|
 |
15
Sapp 2021-01-18 15:19:09 +08:00
我觉得你可以试一下先平均
比如 40 块钱 10 个人，然后取一个范围随机，比如 2 （也就是你的 a ） 到 6 （你的 b ） 之间随机，这样最后总额加起来可能超了，比如 44 多了 4 块钱，那么就每个账户平均一下扣掉超出的金额（ 0.4 ），如果最后加起来少了，比如 36 块钱，就每个账户平均一下加上剩余的 0.4 。 |
|
16
XiaoxiaoPu 2021-01-18 15:20:29 +08:00
@sillydaddy 第一个问题就错了，a1<x1<b1 这个条件被吃了
|
|
17
sillydaddy 2021-01-18 15:32:03 +08:00 via Android
|
|
18
chengfeng1992 2021-01-18 15:33:00 +08:00
|
|
19
chenluo0429 2021-01-18 15:57:58 +08:00 via Android
你可以先想象一下，先给 y 个数字位置都分配 a，那么问题就变成了把数字(x -ya)随机分成 y 个数字，且这些数字满足[0, b - a]。
现在问题就可以转化为，将一个数字 X 分成 y 个数字，这些数字满足[0, A]，其中 X = x -ya, A = b - a 。 再提供一个取巧的方法，应该不是完全随机。 先生成 y 个[0, A]的数字，分别为 a1 到 ay，其和为 C 。然后对原 ai 进行转化，即 ai = ai * C / X 。这个时候 ai 数列的和就大致与 X 相等，将其和与 X 的差值再随机分配给任一个数字即可。如果无法分配则继续往第二第三个数字分。 |
 |
20
FFFire 2021-01-18 16:12:45 +08:00
你首先要明确 a，b 和 x，y 的关系才行，这样就可以用#15 的方法了
|
 |
21
windmelon 2021-01-18 16:15:22 +08:00
想到的简单的方法，但是不知道对随机性有多大影响
即按照每次从[a,b]区间取数的方法每次取一个数，取 Y 次 只不过多一步判断，所取区间的下限是否满足剩余的数都取 b 满足和大于等于 X，否则就提高区间下限[a+,b] |
 |
22
Dvel 2021-01-18 16:23:37 +08:00 1
一个简单的思路：
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)) ``` 优化的时候加一个最后一次直接求结果就行。 |
|
24
chengfeng1992 2021-01-18 17:06:33 +08:00
https://gist.github.com/chengfeng-1992/1ab94bfdab77d395a0dd87b6feb51974
@kaiki @sillydaddy 在#7 想法的基础上，多加了一句判断，测试了下没大问题。 |
|
25
sillydaddy 2021-01-18 17:57:45 +08:00 via Android
@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 。 这说明这种算法不是均匀随机的。 |
 |
26
everhythm 2021-01-18 18:30:40 +08:00
有一个比较简单的预分配的方法：
1. 数字 x 平均分成 y 份 2. random 1 个差值，从 y 份中取出 2 个数，第 1 个加上这个差值，第 2 个减去这个差值，得到的 2 个结果如果满足 >=a 且 <=b，就相当于随机分配了 2 个数字。一直循环到分配完成。 3. 可以 random 多个差值，附加到 y 份中多份数字上 |
 |
27
BiteTheDust 2021-01-18 18:45:07 +08:00
可以先随便分 最后对分好的做一个随机排列 这样期望就是相等的了
|
|
28
chengfeng1992 2021-01-18 19:05:09 +08:00
@sillydaddy #25 试了几组数据，对于某些数据结果数据较为均匀，对于某些数据有较明显的升序或降序特征。说明这确实不是一个好算法。
如果把最终结果再随机排列一次，这种“亡羊补牢”式的做法可取吗？ |
 |
29
h272377502 2021-01-18 21:11:28 +08:00
先在每个红包里先放 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 |
 |
30
JeffGe 2021-01-18 21:28:02 +08:00 via Android
@Dvel 我想了好久，你这个算法严格来说分布不均匀吧。如果严格均匀，那么意味着 10 个随机变量 X1 ~ X10 是轮换对称的对吧，而且这 10 个随机变量应该是同分布的。你这算法第一个随机变量（在合适的参数下）一定是均匀分布的，可他们应该不是同均匀分布的随机变量啊
|
|
31
Dvel 2021-01-18 22:10:23 +08:00
@JeffGe #30 呃我算法渣，没看懂你说的。。。
我试了一下运行 100 万次，然后取每个人的平均数是： 10.00439 10.002429 9.999853 9.998824 9.999526 9.999866 9.996083 10.003026 9.997349 9.998654 |
 |
32
Enix 2021-01-18 22:12:23 +08:00
把很久以前做过的类似的凭印象写了一遍，思路是根据权重分配剩余值（ x - y * a ），大致代码
 |
|
33
Enix 2021-01-18 22:18:06 +08:00
注释一下——
flatten weights 处借助了 `Math.random()` 值域为 0-1 的特点，令 weights 的最值之差减小 `weight * weight` 也许可以改为 `Math.sqrt(weight)` 或其他运算，获得更好的平权效果，没细想 |
|
34
JeffGe 2021-01-18 23:44:50 +08:00 via Android
@Dvel 不是，这不是算法问题，你的算法我认为是一个应对发红包这样一个应用来说挺好的，效率也不错的一个算法。我只是在描述一个数学问题，就像 @sillydaddy 在 8 楼所说的，这是一个在 (n-1) 维的多边形内部随机取一个点的问题，这个多边形投影到一个轴上的函数就是对应随机变量的概率密度分布函数，我觉得这个函数很大可能不是均匀分布函数。你用蒙特卡洛法得到均值为 10 说明不了什么，你应该把累积概率密度图画出来比较一下。
换个实际的例子理解一下，把你的参数微调一下：a=5, b=11，那么如果完全随机的话，是不是按理说 5 的概率较低，10 或 11 的概率要高得多？但是你的算法在第一步给出 X1 随机变量是 [5, 11] 内均匀分布的。 |
 |
35
fbxshit 2021-01-19 00:00:37 +08:00 via iPhone
想了个算法不知道够不够随机：
首先 y 个人随机分配共 x 元，分配完成之后把 y 个人按照财富多少从小到大排列。 最穷的那个人的钱是不是小于 a ？或者最富的那个人的钱是不是大于 b ？如果符合以上条件，把最穷的人和最富的人拉出来，数一下他们的财富相差多少钱，在这个财富差距的数值里面随机取一个数字，让最富的人按照这个数字掏出来把钱补贴给最穷的人，补贴完之后把他们两放回到队伍里，这个时候重新按照财富大小给 y 个人排队，这次最穷的人应该比第一次排序时富了一点，最富的人应该比第一次排序时穷了一点。 不断重复以上步骤，直到最穷的人财富大于等于 a，最富的人财富小于等于 b 。 |
 |
36
msg7086 2021-01-19 03:38:00 +08:00 via Android
先按照给定范围随机取值，取完求和然后二分法等比例带上下限浮动。也就是说比如 10 个人 100 块钱算完是 90 块，可以先每个人上涨 10%，然后约束上限，然后看看还差多少。然后再多涨一点，直到超过 100 块。接下来就是二分法在不到 100 块和超过 100 块之间找一个接近的涨幅即可。精度可以拉到一毛钱，最终误差就加给最高或最低的人即可。
|
 |
37
cassyfar 2021-01-19 03:44:16 +08:00 1
这个需求本生就没法随机。因为有 a，b 限制。比如 x = 10 和 y = 5 的情况下 b = 2，a = 1，那不是只可能有唯一解了，怎么随机呢？
|
|
38
sillydaddy 2021-01-19 14:09:32 +08:00 via Android
|
|
39
sillydaddy 2021-01-19 15:05:17 +08:00 via Android
@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 了。 |
Select Language