Seleccione un elemento al azar, sin saber el número total de elementos

Question

Tengo un caso en el que tengo que seleccionar un elemento al azar, pero no sé el número total de elementos y no quiero construir un gran conjunto luego elige un objeto. Por ejemplo, esto es lo que tengo en este momento:

List<string> items; 
while (true) 
{ 
    string item = GetNextItem(); 
    if (item == null) 
     break; 
} 
int index = random.GetNext(0, items.count); 

Como se puede ver, estoy construyendo una colección gigantesca que realmente no necesito, sólo necesito un número aleatorio entre 0 y el número de artículos. Aquí es lo que estoy pensando en hacerlo, y funciona, pero me gustaría saber si alguno de los expertos por ahí puede encontrar un fallo con él:

int index = -1; 
int total; 
string selectedItem; 
while (true) 
{ 
    string item = GetNextItem(); 
    if (item == null) 
     break; 

    ++total; 
    int rnd = random.Next(0, total); 
    if (rnd == total- 1) 
    { 
     index = total- 1; 
     selectedItem = item; 
    } 
} 

Esto me da a mi número de índice, y el ítem seleccionado al azar. Mi pensamiento detrás de esto es que cuando hay 3 ítems totales, por ejemplo, selecciono un número aleatorio entre 0 y 2 (inclusive) y si es igual a 2 utilizo el nuevo ítem como ítem seleccionado, si no es que simplemente lo ignoro. A medida que aumenta el número total de elementos, la posibilidad de que se seleccione cada nuevo elemento disminuye en consecuencia.

¿Este método es "bueno"? ¿Es tan "aleatorio" como construir la matriz y elegir un elemento más tarde? ¿Es tan rápido como puede ser? Por favor, guíame a través de mi ignorancia en números aleatorios. :)

Answer 1

Lo que estás haciendo funcionará.

Aquí hay una reformulación de la misma que puede hacer que el algoritmo ligeramente más claro:

1. Seleccione el primer elemento, existe la posibilidad de 100% será la selección actual
2. Si hay un segundo artículo, existe una probabilidad de 1/2 de que reemplace la selección actual (si usted hace los cálculos, entonces hay un 50% de posibilidades de que sea el primer elemento, y un 50% de posibilidades de que sea el segundo elemento)
3. Si hay un tercer elemento, hay una posibilidad de 1/3 que sustituirá a la selección actual (de nuevo, los cálculos de la probabilidad de ser cada elemento 1/3)
4. Si hay un cuarto punto , hay la oportunidad 1/4 que sustituirá a la actual selección
5. ... etc ...

en cuenta que debe ser capaz de calcular la oportunidad 1/x diciendo rand.Next(0,x) == 0 (o cualquier otro número entero entre 0 y x - 1 inclusive; no tiene que molestarse en usar total - 1.

En realidad, es un enfoque bastante limpio; ¡Inicialmente pensé que no iba a haber una buena forma de hacer lo que me pedías!

Answer 2

En el primer fragmento de código, utiliza items.count, para que sepa cuántos elementos tiene. Usted necesita para saber este número, de modo que cada elemento tenga las mismas posibilidades de ser seleccionado.

Como escribió, genera un número aleatorio i tal que 0 < = i < items.count, y luego intenta acceder rápidamente al elemento i de la lista. (Una lista vinculada podría no ser una buena opción de estructura de datos.)

Si tiene una buena estimación N del número de elementos, puede usar esto en lugar de items.count.

En su segundo fragmento de código, es posible que deba inicializar "total" en cero.

Answer 3

Su enfoque se ve bien, sí.

1 punto = se selecciona

2 artículos = 50% de posibilidades a escoger el segundo elemento a reemplazar la primera

3 artículos = 33% de posibilidades a escoger el tercero elemento, el 67% de posibilidades de elegir uno de dos primeros elementos

4 artículos = 25% de posibilidades de recoger cuarto elemento, el 75% de posibilidades de recoger ...

...

tan contrario a la mayoría de la junta Aquí hay respuestas que creo que tiene una solución de trabajo que proporciona una distribución de probabilidad pareja.

Usted podría simplificar el control aleatorio:

int rnd = random.Next(0, total); 
    if (rnd == 0) 

Como no importa cuál de Total-1 los valores que prueba para obtener la probabilidad 1/n.

Answer 4

podemos probarlo por inducción.
es cierto para 1;
si es verdadero para n; es cierto para n + 1;
=> prob. de selección para los primeros n elementos = 1/n
=> sice prob. de seleccionar (n + 1) el elemento es 1/(n + 1)
=> problema de no seleccionar (n + 1) el elemento n es n/(n + 1)
=> problema de selección para la primera n elementos después de agregar (n + 1) elemento th = 1/n * (n/n + 1) = 1/n + 1