操作数组, 使得其中相同的元素的距离>=k

[icySoda]

最近业务上的一个需求. 真实场景是这样, 0-31 一共 32 个数, 给定长度 n, 返回一个长度为 n 的随机数组. 使得:

1. 以下元素出现的概率为 50%, 0,7,8,15,16,23,24,31
2. 以下元素出现的概率为 45%: 1~6,25~30, 9,14,17,22
3. 其他元素出现的概率为 5%: 10~14, 18~21
4. 数组中相同元素的位置距离>=6

前 3 点很容易满足, 第 4 点没什么思路, 请老师们指教

[Mutoo]

1 号桶 10 个；
2 号桶 9 个；
3 号桶 1 个；
每个桶对应一个序列，序列里是上面所指定的数字；
初始化的时候将三个序列洗牌；
每回合随机取一个桶，获得相应序列中的首个数字，输出，并将数字放回到序列末尾；
每个序列被取 6 （ k ）次后重新洗牌；

[lysS]

先按前三个要求写一个 rand, rand 每次返回一个值，检查这个值是否符合条件 4 ，不符合重新生成，符合就 append

[icySoda]

@Mutoo 这个并不能保证 4. 前一个回合输出的最后数字是 x, 下一个回合第一个输出的数字也可能是 x.
@lysS 最后一个值运气不好的话, 可能 cpu 冒烟也不一定能得到结果

[Mutoo]

洗牌只发生在初始化和每 k 次 /序列。取的时候只取序列首个数，FIFO 。只要你的序列长度大于 k 就可以保证 4 。

[Mutoo]

更正一下：每号桶对应一个序列，不是每个桶对应一个序列。总的就三个序列。

[ipwx]

@Mutoo 不用放到末尾，加个 next 指针就行。洗牌后，每个桶内每次取 next 指针的数字就行。当 next 指针用完整个桶在重新洗牌。。。

@icySoda 不过这其实和原问题的分布略有不同，但是我觉得足够相近了。这套重新洗牌是最快的实现方案，不然你就得维护过去六个元素的集合，如果下一个采样到的元素属于这个集合就重新采样。。。不过大概也不会太慢。

每个点上重新采样一次的概率是 6/32 ，大概 1/5 。期望采样 2 次就能拿到一个合适的数字。倒也不是不行

[ipwx]

https://ideone.com/oBrYkm

[Mutoo]

写了个代码验证一下，好像确实不能保证 4 。这个规则只有首位数字能保证 k 次不重复。

想了一下，如果有个序列有 7 个数，要保正条件 4 ，生成的结果中每 6 个数都不重复的话，序列就无法随机了。

[Maboroshii]

最简单的想到，如果 n<=6 ，那么不允许出现重复数字
也就是这个结果和 n 的大小相关的，这个完全影响了随机出现

一个蠢办法，离线算出来出符合第 4 点的有限多的数组，最后从这些数组里面随机一个拿出来用就行了

[Maboroshii]

想到一个生成的办法

初始化一个空数组（长度大大于 n)
do {
随机一个数 a
判断这个数是否在数组中
if 存在数 a0 == a {
把这个数放在 a0 位置的 6 位以后 （如果数组长度不够，扩展数组长度）
} else {
放在第一个不为空的位置
}
} while 从数组开始能取到长度为 n 的元素都不为空的片段

这样可以搞一个长度为 n 的窗口，可以一直得到符合要求的数组

[GuuJiang]

每生成一个数，就在接下来的 6 次随机中从随机池中暂时移除，6 次以后再加回来
生成每个数时如果随机到了一个已被移除的数则重试

[ipwx]

@Maboroshii
@Mutoo
@GuuJiang

你看我 7L 的代码，还有 6L 的分析。从期望这只要多采样一倍就行。。。估计是最合适的方案了

加上计数器统计总共的采样次数：

https://ideone.com/e1Ek8y

可以知道这次实验，生成 100 个数字只需要采样 129 次，丢弃率只有不到 30%

[icySoda]

@Maboroshii 这样没法保证数组的前 n 个符合概率要求吧?
@ipwx 这是个办法, 就是概率有点出入, 不过我可以离线算几组概率和要求比较近的拿来用

[ipwx]

@icySoda 我的代码方法没有出入，完全按照楼主的要求来。

[ipwx]

顺便这叫 reject sampling

https://blog.csdn.net/jteng/article/details/54344766

[GuuJiang]

“移除”和“加回来”只是形象的说法，实际实现时只需要记录每个数字最后出现位置，随机结果中检查距离最后出现位置是否小于 6 ，如果是则重试
预判到可能会有人怀疑这样改变了概率，其实不会，根据规则定义，6 次之内出现过的数据概率本来就只能为 0 ，而其他的数仍然是原始的概率，如果不相信的话思考下下面这个简化的例子就明白了
只用一个 6 面骰子，如何产生 1-5 的均匀分布随机数，答案就是如果扔到 6 就不算，重新扔一次，通过条件概率可以很容易计算出这样操作产生的随机数就是 1-5 均匀分布，简单地说就是对于一个随机试验，抛弃某些特定的结果不会影响未被抛弃的那些结果的概率

[icySoda]

@ipwx 你的循环以"是否满足第四点"为跳出的条件, 会导致数量最多的第 2 点的数据概率偏大.
我离线算了几组, 第 2 点所列的元素概率大体都在 50%左右

[Mutoo]

重采样必然会影响概率。至于影响多少很难讲。
@ipwx

[icySoda]

@GuuJiang 我要消化一下😂

[GuuJiang]

@Mutoo 不会影响的，我给的方案也是同一个思路，用条件概率公式简单算一下就知道了

[ipwx]

@Mutoo @icySoda 你们说得对，我把一个重采样的丢弃操作放错位置了。

https://ideone.com/fx3OHz

@icySoda 这个就符合条件了。

reject sampling 是有理论证明的，无需怀疑。如果结果不符合，一定是 reject sampling 没写对（滑稽）

[ipwx]

('accept rate:', 0.6822678583611926)
[0.50017, 0.45079, 0.04904]

接受率在 0.7 左右，比我想的 0.5 要好 hhh

[ipwx]

@icySoda 另外你的 原问题，14 这个数同时出现在 Group B 和 group C 了。我把它放进 group C 了

[GuuJiang]

@icySoda 如果你计算生成的结果频率和你期望的不一致，说明你对概率的计算不对，而且我大概能猜到不对在哪，以 5%这组为例，假设你第一次生成了 10 ，那么接下来的 6 次中不可能再有 10 ，但是 11-14 ，18-21 中每个数出现的概率仍然是 5%/8 ，但是你不能再去统计整组的概率，换句话说，前三条规则表面上说的是三个组整体的概率，实际上说的是其中每个元素的概率，拒绝采样保证没有被丢弃的元素的概率不变，但是如果你要让整组的概率仍然维持不变，这和第 4 条是天然相悖的

[ipwx]

@GuuJiang 21L 我 reject sampling 修正了，22L 是实验结果

[icySoda]

@ipwx 看了结果, 概率确实大体相近👍🏻

同样的逻辑, 我用 js 的出来的概率就是差很多, 百思不得其解

https://ideone.com/bp66nl

[crs0910]

@icySoda while true 写错位置了

[icySoda]

@crs0910 😂