操作数组, 使得其中相同的元素的距离>=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 点没什么思路, 请老师们指教

[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 😂