Оптимальный алгоритм для генерации случайного числа R не в ряде чисел N
Мне любопытно знать то, что лучший способ генерировать случайное целое число R, который не находится в обеспеченном наборе целых чисел (R∉N). Я могу думать о нескольких способах сделать это, но я задаюсь вопросом, что Вы все думаете.
3 ответа
Пусть N - размер общей совокупности, а K - размер исключаемой совокупности.
Это зависит от размера множества, из которого вы делаете выборку. Если исключаемое множество намного меньше, чем общее множество, просто выберите случайное число, и если оно находится в исключаемом множестве, выберите его снова. Если хранить исключенное множество в хэш-таблице, то каждая попытка может быть выполнена за время O(1).
Если исключенное множество велико, выберите случайное число R в множестве размера (N - K) и выведите этот выбор как член неисключенных элементов. Если мы будем хранить только дырки в хэш-таблице, ключ к которой задается значением случайного числа, мы можем сгенерировать его за одну выборку за время O(1).
Точка отсечения будет зависеть от размера (N - K)/N, но я подозреваю, что если она не больше .5 или около того, или ваши наборы очень малы, то на практике просто выборка до получения совпадения будет быстрее.
Сгенерируйте случайное число R во всем домене (вычтите размер N из максимального значения), которое вы хотите использовать. Затем переберите все N, меньшие R, и для каждого добавьте 1 к R. Это даст случайное число в домене, которого нет в N.
Учитывая ваше ограниченное описание? Найдите максимальное значение элементов в N. Генерируйте только случайные числа, превышающие это значение.