Оптимальный алгоритм генерации случайного числа R, не входящего в набор чисел N

Question

Мне любопытно узнать, как лучше всего генерировать случайное целое число R, которое не в предоставленном наборе целых чисел (R∉N). Я могу придумать несколько способов сделать это, но мне интересно, что вы все думаете.

Answer 1

Пусть N будет размером общего набора, а K будет размером исключенного набора.

Я зависит от размера набора, из которого вы выбираете. Если исключенный набор намного меньше, чем общий диапазон, просто выберите случайное число, а если оно находится в исключенном наборе, выберите снова. Если мы сохраняем исключенный набор в хеш-таблице, то каждая попытка может быть выполнена за O (1) раз.

Если исключенный набор велик, выберите случайное число R в наборе размера (N - K) и выведите выбор в качестве элемента не исключенных элементов. Если мы храним только дыры в хеш-таблице со значением случайного числа, мы можем сгенерировать это за один образец за время O (1).

Точка среза будет зависеть от размера (N - K) / N, но я подозреваю, что, если это не больше, чем .5 или около того, или если ваши сеты очень малы, просто выборка, пока вы не получите удар, будет быстрее на практике.

Answer 2

Учитывая ваше ограниченное описание?Найдите максимальное значение элементов в N. Генерируйте только случайные числа, которые больше этого.

Answer 3

Создайте случайное число R во всем домене (вычтите размер N из максимального значения), которое вы хотите использовать. Затем переберите все N меньше, чем R, и для каждого добавьте 1 к R. Это даст случайное число в домене, которого нет в N.