Obtener un elemento aleatorio en la lista vinculada de una sola dirección mediante una sola poligonal

Question

Tengo una lista vinculada de una sola dirección sin conocer su tamaño.

Quiero obtener un elemento aleatorio en esta lista, y solo tengo una vez oportunidad de recorrer la lista. (No tengo permitido atravesar dos o más veces)

¿Cuál es el algoritmo para este problema? ¡Gracias!

Answer 1

Esto es sólo reservoir sampling con un depósito de tamaño 1.

Esencialmente es muy simple

1. escoger el primer elemento sin tener en cuenta (para una lista de longitud 1, el primer elemento es siempre la muestra)
2. Para cualquier otro elemento con probabilidad 1/n donde n es el número de elementos observados hasta ahora, reemplaza el elemento ya elegido con el elemento actual en el que se encuentra.

Esto se muestra de manera uniforme, ya que la probabilidad de elegir cualquier elemento al final del día es de 1/n (ejercicio para el lector).

Answer 2

Probablemente sea una pregunta de entrevista. El muestreo de residuos es utilizado por el científico de datos para almacenar datos relevantes en un almacenamiento limitado a partir de una gran cantidad de datos.

Si usted tiene que recoger k elementos de cualquier matriz con los elementos n, tales que la probabilidad de cada elemento de recogida debe ser el mismo (k/n), se siguen dos pasos,

1) almacenar primeros k elementos en el almacenamiento. 2) Cuando el siguiente elemento (k + 1) proviene de la secuencia, obviamente ya no tiene espacio en su colección. Genere un número aleatorio de o a n, si el número aleatorio generado es menor que k supongamos l, reemplace el almacenamiento [ l] con el elemento (k + 1) de la secuencia.

Ahora, volviendo a su pregunta, aquí el tamaño de almacenamiento es 1. Así que elegirá el primer nodo, iterará sobre la lista para el segundo elemento. Ahora genere el número aleatorio, si es 1, deje la muestra sola, de lo contrario cambie el elemento de almacenamiento de la lista

Answer 3

Esta pregunta se puede hacer utilizando el muestreo de yacimientos. Se basa en la elección de k elementos aleatorios de n elementos, pero aquí n puede ser muy grande (que no tiene que caber en la memoria) y (como en su caso) desconocido inicialmente.

La Wikipedia tiene un algoritmo comprensible que cito a continuación:

array R[k]; // result 
integer i, j; 

// fill the reservoir array 
for each i in 1 to k do 
    R[i] := S[i] 
done; 

// replace elements with gradually decreasing probability 
for each i in k+1 to length(S) do 
    j := random(1, i); // important: inclusive range 
    if j <= k then 
     R[j] := S[i] 
    fi 
done 

La pregunta requiere sólo 1 valor, de modo que tomamos k = 1.

aplicación C:

https://ideone.com/txnsas