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

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 到 return 在 [a,b] 上均匀分布的值 interval 为左区间边界，然后为这些值中的每一个引入一个小的随机变化。在两个这样的边界内，我然后尝试放置正确的间隔边界，同时遵守最小宽度要求。但是，我的方法在计算上非常昂贵。

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

Answer 1

一组间隔的变体之一（其他以相同方式生成）。简单但不是很有效： 1.生成一组介于a和b之间的z值。在你的情况下它是 [x1, x2, x3] （升序排序） 2. 将其转换为区间列表：[[x1, x1], [x2, x2], [x3, x3]] 3. 按每个间隔循环：如果其下边界比前一个间隔的上边界大 1 - 增加其上边界。否则，如果它的上边界比下一个区间的下边界小 1 - 减少它的下区间。如果满足此条件的 none - 将间隔分布在任何一侧。如果两者都满足 - 糟糕，运气不好，请从第 1 点开始重试。 4. 重复步骤3，直到所有间隔都是最小W宽，并且在

之后一些（随机数）次

Answer 2

方法 1 - 朴素的随机生成

这是一种低效但简单的方法 - 从 range(a, b) 中取出 z*2 个随机整数，对它们进行排序，配对，然后检查间隔是否都大于或等于 w.重复此 n 次。

请注意，当 z*w 接近 len(range(a, b)) 时，这将是低效的。我确实考虑过通过添加一个辅助函数来生成一个随机的 nth 间隔来缓解这个问题，该间隔将允许创建剩余的 z-n 间隔 - 通过从 range(a, b-w*(z-n)) 中选择索引，但是这会遇到首先选择的间隔将偏向于更长的问题。

代码：

def list_to_pairs(l):
    return [l[i:i+2] for i in range(0, len(l), 2)]

def f(z, w, a, b):
    intervals = [(0,0)]
    while not all(x[1]-x[0] >= w for x in intervals):
        intervals = list_to_pairs(sorted(random.sample(range(a, b), z*2)))
    return intervals

def get_lists(n, z, w, a, b):
    return [f(z, w, a, b) for _ in range(n)]

输出：

>>> get_lists(4, 3, 5, 0, 100)
[[[0, 17], [22, 46], [62, 98]],
 [[10, 32], [61, 66], [72, 81]],
 [[2, 31], [63, 68], [77, 87]],
 [[5, 20], [34, 55], [58, 86]]]

方法二

@Peter O. 概述了一个，它不依赖于我在下面编写的随机选择间隔，并进行了一些小的逻辑更改。

代码：

def positive_integers_with_sum(n, total):
    ls = [0]
    rv = []
    while len(ls) < n:
        c = random.randint(0, total)
        ls.append(c)
    ls = sorted(ls)
    ls.append(total)
    for i in range(1, len(ls)):
        rv.append(ls[i] - ls[i-1])
    return rv

def f(z, w, a, b):
    rv = []
    indices = [x+w for x in positive_integers_with_sum(z, (b-a)-z*w)]
    start = a
    for i in indices:
        i_start = random.randint(start, i+start-w)
        i_end = random.randint(max(i_start+w, i+start-w), i+start)
        rv.append([i_start, i_end - 1])
        start+=i
    return rv

def get_lists(n, z, w, a, b):
    return [f(z, w, a, b) for _ in range(n)]

输出：

>>> get_lists(5, 3, 5, 0, 15)
[[[0, 4], [5, 9], [10, 14]],
 [[0, 4], [5, 9], [10, 14]],
 [[0, 4], [5, 9], [10, 14]],
 [[0, 4], [5, 9], [10, 14]],
 [[0, 4], [5, 9], [10, 14]]]

>>> get_lists(4, 3, 5, 0, 100)
[[[45, 72], [74, 79], [92, 97]],
 [[18, 23], [39, 44], [77, 97]],
 [[12, 31], [37, 53], [83, 95]],
 [[13, 46], [62, 87], [94, 100]]]

区间平均尺寸：

rv = [[],[],[]]

for i in range(100000):
    t = f(3,5,0,100)
    for i in range(3):
        rv[i].append(abs(t[i][1] - t[i][0]))

输出：

>>> np.mean(rv, axis=1)
array([16.10771, 16.35467, 16.21329])

Answer 3

这是建议算法的草图：

生成 z 个非负整数（整数 0 或更大），总和为 ((b-a)+1) - z*w。我已经根据 Smith 和 Tromble 的 "Sampling Uniformly from the Unit Simplex".

pseudocode

将 w 添加到以这种方式生成的每个数字。这导致 z 个连续候选区间的大小。
在每个候选区间内生成一个具有最小长度 w 的随机子区间。这些子区间是算法的实际输出。每个子间隔相应地移动 a 及其候选间隔的开始。

Answer 4

这是一个构建间隔的版本，因此它们必须满足规范（因此它永远不需要 "keep picking random values until you get lucky"）：

from random import randint
def one_list( a, b, z, w ):
    # How many numbers we have to work with
    nums = b - a - 1 
    # Minimum number of values that will be in some interval
    used = w*z
    # Number of additional values in some interval
    extra = randint( 0, nums - used )
    # Number of values not in any interval
    unused = nums - used - extra
    ans = []
    for _ in range(z):
        # How many values to skip over
        skip = randint(0,unused)
        a += skip
        unused -= skip
        # How many more than minimum to put in next interval
        plus = randint(0,extra)
        ans.append([a,a+w-1+plus])
        a += (w+plus)
        extra -= plus
    return ans

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

Generate multiple sets of random, non-overlapping intervals within a range

python

random

algorithm

intervals

python-3.x

方法 1 - 朴素的随机生成

方法二