c++ - dev - generar letras aleatorias php
Dada una lista de longitud desconocida, devuelve un elemento aleatorio escaneando solo 1 vez (4)
Dada una lista de longitud desconocida, devuelva un elemento aleatorio escaneándolo solo 1 vez.
Mi idea:
Un algoritmo similar es el Muestreo de Yacimientos (publicado por otros). Pero es demasiado complicado porque necesita ejecutar rand () y mantener k nodos en cada iteración.
¿Hay una mejor solución? O (n) tiempo y O (1) espacio?
¿Por qué estás en contra del muestreo de yacimientos? Lo haces con k = 1. Hay optimizaciones menores (por ejemplo, no necesitas seleccionar 1 de la k, ya que k = 1) pero es el enfoque correcto. Puede tratar de optimizar manteniendo el procesamiento de una ventana fija a la vez, hacer los cálculos para determinar con la misma probabilidad si debe elegir cualquiera de los elementos en su ventana en lugar de la que tiene, etc. para minimizar las llamadas rand () al costo de un algoritmo más complicado, pero de todos modos terminarás haciendo un muestreo de yacimientos.
Solución en C (implementación del muestreo de yacimientos con k = 1): es posible que desee utilizar "sin signo de larga duración" para contar.
unsigned int chosen, num, count;
count = 1;
get_number(&chosen);
while (get_number(&num)) {
count++;
if (rand() % n == 0) chosen = num;
}
Mantener k nodos por iteración es fácil, cuando k = 1.
Funciona rand () cada vez, que es algo pesado. Puede obtener resultados razonables con una función pseudoaleatoria mucho más simple. Pero esto haría que el código sea más complicado, no más simple.
Vea el libro de cocina de Perl para el algoritmo , que se adaptará fácilmente a C ++.
Básicamente, escanee la lista una vez, y para cada entrada con índice que lea, guárdela si un número aleatorio entre 0 e i + 1 es menor que 1.
El resultado es la última entrada guardada.
Utiliza el muestreo de yacimientos .
Esto no es muy complicado ni costoso; es el enfoque mínimo dadas las restricciones que tiene (seleccionando un elemento de un flujo).
Funciona bien si quieres un tamaño de muestra aleatorio de 1 y si todos los elementos tienen el mismo peso.
Cuando ha simplificado el código con una KB de 1 y no tiene ponderaciones explícitas, sigue siendo un muestreo de yacimientos.
No todos los generadores de números pseudoaleatorios se ejecutan a la misma velocidad; elige uno rápido
Los comentarios preguntan qué pasaría si reutilizaras el mismo número aleatorio en lugar de generar un nuevo número aleatorio en cada paso:
El enlace de Wikipedia dado muestra la equivalencia con la mezcla aleatoria de Yates-Fisher / Knuth. Si preguntaras qué elegiría el mismo número aleatorio en cada paso de la barajadura, estarías ladrando.