Se nos da un generador de números aleatorios RandNum50
que genera un entero aleatorio uniformemente en el rango 1-50. Podemos usar solo este generador de números aleatorios para generar e imprimir todos los enteros del 1 al 100 en un orden aleatorio. Cada número debe venir exactamente una vez, y la probabilidad de que ocurra cualquier número en cualquier lugar debe ser igual.
¿Cuál es el algoritmo más eficiente para esto?
algorithms
integers
randomness
random-number-generator
Raj Wadhwa
fuente
fuente
RandNum100 = (RandNum50() * 2) - (RandNum50 > 25) ? 0 : 1)
.Respuestas:
Pensé (por lo que puede estar equivocado :-) de esta solución que usa el shuffle de Fisher-Yates . Para mantener una distribución uniforme con una buena aproximación (consulte la sección EDITAR a continuación) en cada iteración, puede usar este truco para producir un valor entre 0 y k - 1 :O(N2) 0 k−1
krand
El algoritmo de Fisher-Yates se convierte en:
EDITAR:
krand
fuente
Dado que otras personas han dado soluciones aproximadas y soluciones que implican tomar números indeterminados de desviaciones, ¿qué tal una prueba de que no existe tal algoritmo que garantice que solo requiera un número finito de
RandNum50()
llamadas?RandNum50
RandNum50
RandNum50
fuente
Si no sabe cómo generar un uniforme, como se sugiere en esa publicación, a partir de un bit aleatorio, también podría generar una aproximación del uniforme directamente, de esta manera (que es equivalente al "verdadero y" de Vor, pero más rápido):
fuente
No he hecho el análisis para confirmar qué tan uniforme (o no) sería esto, y podría ajustarse para que sea una mezcla aleatoria verdadera, pero ¿podría elegir, desde una matriz inicial del
i
índice th =i + 1
, el(k + RandNum50() + RandNum50() - 1) mod (100 - k)
índice, con eliminación, parak
= 0..99?Esto "empuja" el pico en la
RandNum50() + RandNum50()
distribución hacia adelante de manera uniforme.Estoy bastante seguro de que esto no es del todo correcto, ya que lo he dicho porque el índice 0 (1) no se puede obtener de la primera opción y no puedo ver rápidamente un ajuste alternativo 1..50 + 1..50 que produzca 0 ..99.
Actualizar
Para solucionar el problema que noté, utilicé efectivamente
RandNum100
como se menciona en los comentarios de la pregunta para inicializar aleatoriamente el primerk
desplazamiento.Esto produce una distribución con una onda significativa en el frente.
En lugar de avanzar por 1, usé otro
RandNum50
para incrementar eso primerok
. Esto produce un resultado que es lo suficientemente aleatorio para mí, pero todavía no es "verdaderamente" aleatorio, como se puede ver fácilmente si cambia K a 2.Probar el código VB.NET donde atendí a cualquier K. Tenga en cuenta que es O (K), 6K + 2, de hecho.
fuente