algorithm - segunda - estrategia de reemplazo sistemas operativos

Algoritmo óptimo para generar un número aleatorio R no en un conjunto de números N

Question

Tengo curiosidad por saber cuál es la mejor forma de generar un entero aleatorio R que no esté en un conjunto proporcionado de enteros (R∉N). Puedo pensar en varias formas de hacerlo, pero me pregunto qué piensan todos ustedes.

Answer 1

Dada su descripción limitada? Encuentre el valor máximo de los elementos en N. Genere solo números aleatorios mayores que eso.

Answer 2

Deje N ser del tamaño del conjunto general, y deje K sea el tamaño del conjunto excluido.

Depende del tamaño del conjunto del que estás tomando muestras. Si el conjunto excluido es mucho más pequeño que el rango general, simplemente elija un número aleatorio, y si está en el conjunto excluido, elija nuevamente. Si mantenemos el conjunto excluido en una tabla hash, cada intento se puede realizar en O (1) vez.

Si el conjunto excluido es grande, elija un número aleatorio R en un conjunto de tamaño (N - K) y dé como resultado la opción como el miembro de los elementos no excluidos. Si almacenamos solo los agujeros en una tabla hash marcada con el valor del número aleatorio, podemos generar esto en una muestra en el tiempo O (1).

El punto de corte dependerá del tamaño de (N - K) / N, pero sospecho que a menos que sea mayor de .5 o más, o los conjuntos son muy pequeños, solo el muestreo hasta obtener un golpe será más rápido en la práctica .

Answer 3

Genere un número aleatorio R en todo el dominio (reste el tamaño de N del valor máximo) que desee usar. Luego recorra todo N menos que R y para cada uno agregue 1 a R. Esto dará un número aleatorio en el dominio que no está en N.