¿Cómo seleccionar uno de n objetos al azar sin saber n al principio?

Question

Para concretar, ¿cómo leerías la línea de texto, y seleccionarías e imprimirías una línea al azar, cuando no sabes el número de líneas por adelantado?

Sí, este es un problema de la perla de programación que me confunde.

La solución elige el primer elemento, luego selecciona el segundo con probabilidad 1/2, el tercero con 1/3, y así sucesivamente.

Un algoritmo:

i = 0 
while more input lines 
    with probability 1.0/++i 
    choice = this input line 
print choice 

Supongamos que la elección final es el tercero elemento, la probabilidad es 1 x 1/2 x 1/3 x 3/4 x ... x n-2/n-1 x n-1/n == 1/2n? Pero 1/n debería ser correcto.

Answer 1

Su algoritmo es correcto, pero el análisis no lo es. Puedes probarlo por inducción. Sin apretar: Funciona para N = 1, por supuesto. Si funciona hasta N-1, ¿qué sucede en N? La probabilidad de que se elija el N-ésimo elemento y sobrescriba la última opción es 1/N - bueno. La posibilidad de que no lo sea es (N-1)/N. En cuyo caso, se utiliza la elección del paso anterior. Pero en ese punto, todos los elementos tenían una posibilidad 1/(N-1) de ser elegidos. Ahora es 1/N. Bueno.

Answer 2

Esto no es verdaderamente aleatorio, ya que es más probable que elija una línea al principio del archivo. Necesita saber el número de líneas para hacerlo al azar. (¡50% de las veces obtiene la primera línea!)

Answer 3

Método 1: Haga una primera pasada para determinar cuántas líneas hay. Luego al azar.

Método 2: Use el método que mencionó. Funciona, pero no le dará a cada línea la misma posibilidad de ser seleccionado.

Por lo que puedo decir, no es posible ajustar el método 2 para dar a cada línea la misma posibilidad de ser elegido. Es matemáticamente posible que la cantidad de líneas sea ilimitada hasta el infinito.

Answer 4

Su cálculo es erróneo:

Supongamos que la elección final es el tercero elemento, la probabilidad es 1 x 1/2 x 1/3 x 3/4 x ... x n-2/n-1 x n-1/n

La probabilidad real es:

(1 x 1/2 + 1 x 1/2) x 1/3 x 3/4 x .. .x n-2/n-1 x n-1/n == 1/n

ya sea que eligieron 2 o si no eligió 2 (chosing 2 tiene una proba de 1/2 y no eligiendo 2 A Proba de media)

Answer 5

Leer 1 Leer 2 50% de probabilidad de cualquiera , mantén uno, descarta uno. Lea 3 (debemos tener 1 y 3 o 2 y 3). 50% de probabilidad de cualquiera de las líneas, descarte la otra. Siga trabajando con un 50% de probabilidad en todo el archivo, esto le deja con 2 líneas. Tome un 50/50 en cualquiera de las líneas y tiene una línea aleatoria. Las probabilidades eran iguales para todo el archivo.