¿Cómo elegirías un elemento aleatorio uniforme en la lista vinculada con longitud desconocida en una pasada o si no en dos?¿Cómo elegirías un elemento aleatorio uniforme en la lista vinculada con longitud desconocida?
Utilice el muestreo de depósito http://en.wikipedia.org/wiki/Reservoir_sampling. Solo necesita una pasada de los datos.
Para recoger un elemento:
Le demostraré que esto da como resultado una selección uniforme de elementos.
Intenté usar eso, pero esto elegirá k elementos aleatorios. pero solo necesitaré seleccionar el primer elemento – exlux15
@AnilBabooram Use k = 1? De todos modos, el algoritmo mencionado en la publicación (no wiki) es para un caso de elemento. – ElKamina
ok si uso un ciclo while along ++ length para recorrer la lista. Si uso i = rand()% de longitud, ¿"yo" sería la elección aleatoria en el nodo actual? – exlux15
Me temo que tendrá que poner un poco más de esfuerzo en su pregunta y dejar en claro lo que está pidiendo –
bien. ¿cómo elegirías un elemento aleatorio uniforme en la lista vinculada con longitud desconocida? – exlux15
Si esa es su pregunta, es una pregunta interesante. Por favor, edite su pregunta en consecuencia y lo revocaré –