python - 在一个范围内生成多组随机的、不重叠的间隔

Question

在特定的整数范围内 [a, b] 我想生成 n 列表，每个列表由 z 组成，不重叠，最小间隔宽度为 w 的随机间隔。非重叠条件应在单个此类列表中理解。

a=0, b=100, n=4, z=3, w=5 的示例:

1. [ [1, 17], [57, 83], [89, 98] ]
2. [ [5, 23], [42, 49], [60, 78] ]
3. [ [70, 76], [80, 89], [93, 99] ]
4. [ [20, 62], [67, 81], [82, 93] ]

目前我使用 numpy.linspace 在 [a,b] 上返回均匀间隔的值 interval 为左区间边界，然后为这些值中的每一个引入一个小的随机变化。 在两个这样的边界内，我然后尝试放置正确的间隔边界，同时遵守最小宽度要求。但是，我的方法在计算上非常昂贵。

在 Python 中实现我的目标的最有效方法是什么？

Answer 1

这是一个建议算法的草图:

1. 生成总和为 ((b-a)+1) - z*w 的 z 非负整数(0 或更大的整数)。我写了pseudocode此算法基于 Smith 和 Tromble 的“从单位单纯形均匀采样”。
2. 将 w 添加到以这种方式生成的每个数字中。这导致 z 连续候选区间的大小。
3. 在每个候选区间内生成一个具有最小长度 w 的随机子区间。这些子区间是算法的实际输出。每个子区间相应地移动 a 及其候选区间的开始。