Создание нескольких наборов случайных неперекрывающихся интервалов в пределах диапазона

Вот набросок предлагаемого алгоритма:

1. Сгенерируйте z неотрицательные целые числа (целые числа 0 или больше) с суммой ((b-a)+1) - z*w. Я написал псевдокод для этого алгоритма, основанный на "Равномерной выборке из модуля" Смита и Тромбла. Симплекс ».
2. Добавьте w к каждому числу, сгенерированному таким образом. Это приводит к размеру z непрерывных интервалов кандидатов.
3. Создайте случайный подинтервал с минимальной длиной w внутри каждого интервала кандидата. Эти подинтервалы являются фактическим результатом работы алгоритма. Каждый подынтервал сдвигается соответственно на a и начало своего предполагаемого интервала.

Подход 1 - Наивная случайная генерация

Это неэффективный, но простой подход - возьмите z*2 случайные целые числа из range(a, b), отсортируйте их, объедините в пары и проверьте, все ли интервалы больше или равны 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]]]

Подход 2

@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])

Один из вариантов для одного набора интервалов (остальные генерируются аналогично). Просто, но не очень эффективно: 1. Создайте набор значений z между a и b. В вашем случае это [x1, x2, x3] (отсортировано по возрастанию) 2. Преобразуйте его в список интервалов: [[x1, x1], [x2, x2], [x3, x3]]] 3. Цикл по каждому интервалу: если его нижняя граница на 1 больше верхней границы предыдущего интервала - увеличьте его верхнюю границу. Иначе, если его верхняя граница на 1 меньше нижней границы следующего интервала - уменьшите его нижний интервал. Если ни одно из этих условий не соблюдается - раздвиньте интервал в любую сторону. Если оба соблюдены - ой, неудача, попробуйте еще раз с пункта 1. 4. Повторяйте шаг 3, пока все интервалы не станут минимальной шириной W, и несколько (случайное число) раз после

Вот версия, которая строит интервалы таким образом, чтобы они соответствовали спецификациям (так что никогда не нужно «продолжать выбирать случайные значения, пока вам не повезет»):

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