Tengo curiosidad por saber cuál es la mejor forma de generar un entero aleatorio R que sea no en un conjunto proporcionado de enteros (R∉N). Puedo pensar en varias formas de hacerlo, pero me pregunto qué piensan todos ustedes.Algoritmo óptimo para generar un número aleatorio R no en un conjunto de números N
Deje que N sea el tamaño del conjunto general, y deje que K sea el tamaño del conjunto excluido.
Depende del tamaño del conjunto del que está tomando la muestra. 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 menos, o los conjuntos son muy pequeños, solo muestrear hasta obtener un golpe lo hará ser más rápido en la práctica.
+1 - mostró los casos selectivo y restrictivo. – aperkins
wow muy buenas soluciones – Alan
Buena respuesta en principio, pero no estoy seguro de eso 0.9 umbral --- Creo que podría ser significativamente más bajo en muchos casos y comenzaría a sentirse bastante incómodo a aproximadamente 0.5. Supongo que solo puedes probarlo en tu aplicación, pero en caso de duda, preferiría el tiempo de ejecución determinista. – Svante
Genere un número aleatorio R en todo el dominio (restar el tamaño de N del valor máximo) que desea 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.
Esa no es la verdadera generación aleatoria, ya que se ponderará hacia los números de borde: números que están cerca de los elementos en N. – aperkins
No, no lo hará porque agrega 1 a R si hay un conflicto o no. – murgatroid99
Sí, razón por la cual terminará alrededor de los bordes; es más probable que su R sea la que está justo encima de uno en el conjunto de N que no, el doble de probabilidades. Pulsar un número justo encima de otro se convertiría en 2/P, donde P es el conjunto completo de números disponibles, y todos los demás números serían 1/P. Si tenía números en una fila, digamos 2,3,4, en el conjunto, entonces, para cada número en una fila, la posibilidad de golpear a la que está encima (4 en este ejemplo) aumenta en 1/P por cada número. una fila después de la primera (4/P en mi ejemplo). – aperkins
¿Dada tu descripción limitada? Encuentre el valor máximo de los elementos en N. Genere solo números aleatorios mayores que eso.
Depende de cuán discretos sean sus conjuntos. ¿Cuál es más parecido a lo que quieres ?: (1) Generar un entero aleatorio entre 1 y 50, pero no 4,5, o 6 o (2) Generar un doble aleatorio entre 0.0 y 1.0, pero no entre 0.1 y 0.2 – Justin
I Lamento no haber aclarado eso. R es un número entero y cada número en N es un número entero. – Alan