Генерация случайного числа, но исключение нескольких диапазонов без зацикливания - PullRequest
Новая
       12

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

0 голосов
/ 04 марта 2020

Я ищу математический подход для генерации случайного числа между [a, b) с отверстиями в [c, d), [e, f), [g, h) и т. Д., Где a < b и диапазоны находятся в границах.

Я нашел здесь множество примеров того, как заставить алгоритм работать, если есть один пропущенный диапазон, но, похоже, не удается найти эффективный в пространстве / времени подход, который обобщает на несколько диапазонов. Я имею в виду, что оба:

a. Список всех возможных диапазонов и выбор из этого списка: не подходит для больших диапазонов

b. Генерация случайного числа и проверка, является ли он одним из диапазонов, в противном случае повторная попытка: неограниченные условия выполнения

Некоторые существенные тестовые случаи могут быть: 

generate_random(start=0, end=100, exclude: [(2,50),(51, 100)])
generate_random(start=0, end=1e16, exclude: [(1e6,1e7),(1e3, 1e4)])

Вот некоторые из примеров Я нашел:

Ответы [ 2 ]

1 голос
/ 04 марта 2020

Итак, вы хотите выбрать любой из a..c-1, d..e-1, ..., x..b-1?

Итак N = (c-a) + (e-d) + ... + (b - x). Выберите случайный r в 0..N-1. Если r < c, все готово. Установите r = r + d, если r < e, все готово ...

0 голосов
/ 04 марта 2020

Ниже приведена Python реализация вышеуказанного алгоритма из ответа @Chris Hall 

def random_exclude(low: int, high: int, exclude: List[Tuple[int]]) -> int:
  N = -low+sum([(l-h) for l,h in exclude])+high
  r = np.random.randint(low, N)
  for l, h in exclude:
    if r < l:
      return r
    else:
      r+=h
  return r
...