这是一个创建于 1051 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近业务上的一个需求. 真实场景是这样, 0-31 一共 32 个数, 给定长度 n, 返回一个长度为 n 的随机数组. 使得:
- 以下元素出现的概率为 50%, 0,7,8,15,16,23,24,31
- 以下元素出现的概率为 45%: 1~6,25~30, 9,14,17,22
- 其他元素出现的概率为 5%: 10~14, 18~21
- 数组中相同元素的位置距离>=6
前 3 点很容易满足, 第 4 点没什么思路, 请老师们指教
 |
1
Mutoo 2021-12-23 12:26:51 +08:00
1 号桶 10 个；
2 号桶 9 个； 3 号桶 1 个； 每个桶对应一个序列，序列里是上面所指定的数字； 初始化的时候将三个序列洗牌； 每回合随机取一个桶，获得相应序列中的首个数字，输出，并将数字放回到序列末尾； 每个序列被取 6 （ k ）次后重新洗牌； |
 |
2
lysS 2021-12-23 12:40:41 +08:00
先按前三个要求写一个 rand, rand 每次返回一个值，检查这个值是否符合条件 4 ，不符合重新生成，符合就 append
|
 |
3
icySoda OP |
|
4
Mutoo 2021-12-23 13:37:50 +08:00 via iPhone
洗牌只发生在初始化和每 k 次 /序列。取的时候只取序列首个数，FIFO 。只要你的序列长度大于 k 就可以保证 4 。
|
|
5
Mutoo 2021-12-23 13:39:20 +08:00 via iPhone
更正一下：每号桶对应一个序列，不是每个桶对应一个序列。总的就三个序列。
|
 |
6
ipwx 2021-12-23 13:46:30 +08:00
|
|
7
ipwx 2021-12-23 13:52:05 +08:00
|
|
8
Mutoo 2021-12-23 14:11:34 +08:00
写了个代码验证一下，好像确实不能保证 4 。这个规则只有首位数字能保证 k 次不重复。
想了一下，如果有个序列有 7 个数，要保正条件 4 ，生成的结果中每 6 个数都不重复的话，序列就无法随机了。 |
 |
9
Maboroshii 2021-12-23 14:32:31 +08:00
最简单的想到，如果 n<=6 ，那么不允许出现重复数字
也就是这个结果和 n 的大小相关的，这个完全影响了随机出现 一个蠢办法，离线算出来出符合第 4 点的有限多的数组，最后从这些数组里面随机一个拿出来用就行了 |
|
10
Maboroshii 2021-12-23 14:41:44 +08:00
想到一个生成的办法
初始化一个空数组（长度大大于 n) do { 随机一个数 a 判断这个数是否在数组中 if 存在数 a0 == a { 把这个数放在 a0 位置的 6 位以后 （如果数组长度不够，扩展数组长度） } else { 放在第一个不为空的位置 } } while 从数组开始能取到长度为 n 的元素都不为空的片段 这样可以搞一个长度为 n 的窗口，可以一直得到符合要求的数组 |
 |
11
GuuJiang 2021-12-23 15:15:16 +08:00
每生成一个数，就在接下来的 6 次随机中从随机池中暂时移除，6 次以后再加回来
生成每个数时如果随机到了一个已被移除的数则重试 |
|
12
ipwx 2021-12-23 15:23:23 +08:00
@Maboroshii
@Mutoo @GuuJiang 你看我 7L 的代码，还有 6L 的分析。从期望这只要多采样一倍就行。。。估计是最合适的方案了 加上计数器统计总共的采样次数： https://ideone.com/e1Ek8y 可以知道这次实验，生成 100 个数字只需要采样 129 次，丢弃率只有不到 30% |
|
13
icySoda OP |
|
15
ipwx 2021-12-23 15:25:03 +08:00
|
|
16
GuuJiang 2021-12-23 15:27:21 +08:00
“移除”和“加回来”只是形象的说法，实际实现时只需要记录每个数字最后出现位置，随机结果中检查距离最后出现位置是否小于 6 ，如果是则重试
预判到可能会有人怀疑这样改变了概率，其实不会，根据规则定义，6 次之内出现过的数据概率本来就只能为 0 ，而其他的数仍然是原始的概率，如果不相信的话思考下下面这个简化的例子就明白了 只用一个 6 面骰子，如何产生 1-5 的均匀分布随机数，答案就是如果扔到 6 就不算，重新扔一次，通过条件概率可以很容易计算出这样操作产生的随机数就是 1-5 均匀分布，简单地说就是对于一个随机试验，抛弃某些特定的结果不会影响未被抛弃的那些结果的概率 |
|
17
icySoda OP @ipwx 你的循环以"是否满足第四点"为跳出的条件, 会导致数量最多的第 2 点的数据概率偏大.
我离线算了几组, 第 2 点所列的元素概率大体都在 50%左右 |
|
21
ipwx 2021-12-23 15:54:46 +08:00
@Mutoo @icySoda 你们说得对，我把一个重采样的丢弃操作放错位置了。
https://ideone.com/fx3OHz @icySoda 这个就符合条件了。 reject sampling 是有理论证明的，无需怀疑。如果结果不符合，一定是 reject sampling 没写对（滑稽） |
|
22
ipwx 2021-12-23 15:56:05 +08:00
('accept rate:', 0.6822678583611926)
[0.50017, 0.45079, 0.04904] 接受率在 0.7 左右，比我想的 0.5 要好 hhh |
|
23
ipwx 2021-12-23 15:57:02 +08:00
@icySoda 另外你的 原问题，14 这个数同时出现在 Group B 和 group C 了。我把它放进 group C 了
|
|
24
GuuJiang 2021-12-23 15:58:04 +08:00
@icySoda 如果你计算生成的结果频率和你期望的不一致，说明你对概率的计算不对，而且我大概能猜到不对在哪，以 5%这组为例，假设你第一次生成了 10 ，那么接下来的 6 次中不可能再有 10 ，但是 11-14 ，18-21 中每个数出现的概率仍然是 5%/8 ，但是你不能再去统计整组的概率，换句话说，前三条规则表面上说的是三个组整体的概率，实际上说的是其中每个元素的概率，拒绝采样保证没有被丢弃的元素的概率不变，但是如果你要让整组的概率仍然维持不变，这和第 4 条是天然相悖的
|
1 |
26
icySoda OP |
Select Language