Мне любопытно узнать, какой лучший способ генерировать случайное целое число R, которое равно , а не в предоставленном наборе целых чисел (R∉N). Я могу придумать несколько способов сделать это, но мне интересно, что вы все думаете.Оптимальный алгоритм для генерации случайного числа R не в наборе чисел N
Пусть N - размер общего набора, а K - размер исключенного набора.
В зависимости от размера набора, из которого вы взяли выборку. Если исключенный набор намного меньше общего диапазона, просто выберите случайное число, и если он находится в исключенном наборе, выберите снова. Если мы сохраним исключенный набор в хеш-таблице, каждая попытка может быть выполнена в O (1) раз.
Если исключенный набор является большим, выберите случайное число R в наборе размеров (N - K) и выведите выбор как элемент исключенных элементов. Если мы храним только отверстия в хеш-таблице с ключом со случайным числом, мы можем сгенерировать это в один образец за время O (1).
Точка отсечки будет зависеть от размера (N - K)/N, но я подозреваю, что если это не больше 0,5 или около того, или вы наборы очень малы, просто выборка, пока вы не получите удар, будет Быть быстрее на практике.
+1 - показал как выборочные, так и ограничительные случаи. – aperkins
wow очень хорошие решения – Alan
Хороший ответ в принципе, но я не был бы уверен в этом 0.9 - я думаю, что во многих случаях он может быть значительно ниже и начнет чувствовать себя довольно непросто около 0,5. Я предполагаю, что вы можете протестировать его только в своем приложении, но, если сомневаетесь, я бы предпочел детерминированное время выполнения. – Svante
Создайте случайное число R во всем домене (вычтите размер N из максимального значения), которое вы хотите использовать. Затем проведите через все N меньше, чем R, и для каждого добавить 1 в R. Это даст случайное число в области, которая не находится в N.
Это не истинное случайное поколение, потому что оно будет взвешено по отношению к номерам краев - числа, которые находятся рядом с элементами в N. – aperkins
Нет, это не так, потому что добавляет 1 к R, есть ли конфликт. – murgatroid99
Да, вот почему это закончится вокруг краев - ваш R будет более вероятным быть тем, который находится выше одного в наборе N, а не в два раза. Чтобы попасть в число справа над другим, это станет 2/P, где P - весь набор доступных номеров, а все остальные числа будут 1/P. Если у вас были числа в строке - скажем, 2,3,4 - в наборе, то для каждого числа в строке вероятность попадания над ним выше (4 в этом примере) увеличивается на 1/P на номер в строка после первого (4/P в моем примере). – aperkins
С учетом вашего ограниченного описания? Найдите максимальное значение элементов в N. Создайте только случайные числа, большие, чем это.
Это зависит от того, насколько дискретны ваши наборы. Который больше похож на то, что вы хотите ?: (1) Генерировать случайное целое число от 1 до 50, но не 4,5 или 6 или (2) Создать случайное двойное от 0,0 до 1,0, но не между 0,1 и 0,2 – Justin
I Мне жаль, что я не уточнил это. R - целое число, и каждое число из N является целым числом. – Alan