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

Question

В пределах указанного c целочисленного диапазона [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] для границ левого интервала, а затем ввести небольшое случайное изменение для каждого из этих значений. Затем в двух таких границах я пытаюсь установить правильные границы интервала, соблюдая при этом требование минимальной ширины. Однако мой подход очень затратен в вычислительном отношении.

Какой самый эффективный способ достижения моей цели в Python?

Answer 1

Вот эскиз предлагаемого алгоритма:

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

Answer 2

Подход 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

@ Питер О. обрисовал в общих чертах лучший алгоритм , который не основан на случайных интервалах выбора, которые я кодировал ниже с несколькими незначительными изменениями логики c.

Код:

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

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

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

Answer 4

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