Dada una lista enlazada individualmente, seleccione un Node aleatorio de la lista enlazada (la probabilidad de elegir un Node debe ser 1/N si hay N Nodes en la lista). Se le da un generador de números aleatorios.
A continuación se muestra una solución simple:
- Cuente el número de Nodes recorriendo la lista.
- Recorra la lista nuevamente y seleccione cada Node con probabilidad 1/N. La selección se puede hacer generando un número aleatorio de 0 a Ni para el i-ésimo Node, y seleccionando el i-ésimo Node solo si el número generado es igual a 0 (o cualquier otro número fijo de 0 a Ni).
Obtenemos probabilidades uniformes con los esquemas anteriores.
i = 1, probability of selecting first node = 1/N i = 2, probability of selecting second node = [probability that first node is not selected] * [probability that second node is selected] = ((N-1)/N)* 1/(N-1) = 1/N
De manera similar, las probabilidades de que otros seleccionen otros Nodes son 1/N.
La solución anterior requiere dos recorridos de la lista enlazada.
¿Cómo seleccionar un Node aleatorio con solo un recorrido permitido?
La idea es utilizar Reservoir Sampling . Los siguientes son los pasos. Esta es una versión más simple de Reservoir Sampling ya que necesitamos seleccionar solo una tecla en lugar de k teclas.
(1) Initialize result as first node result = head->key (2) Initialize n = 2 (3) Now one by one consider all nodes from 2nd node onward. (a) Generate a random number from 0 to n-1. Let the generated random number is j. (b) If j is equal to 0 (we could choose other fixed numbers between 0 to n-1), then replace result with the current node. (c) n = n+1 (d) current = current->next
A continuación se muestra la implementación del algoritmo anterior.
Javascript
<script> // Javascript program to select a random // node from singly linked list // Node Class class Node { constructor(d) { this.data=d; this.next = null; } } // A reservoir sampling-based function // to print a random node from a // linked list function printrandom(node) { // If list is empty if (node == null) { return; } // Use a different seed value so // that we don't get same result // each time we run this program // Math.abs(UUID.randomUUID(). // getMostSignificantBits()); // Initialize result as first node let result = node.data; // Iterate from the (k+1)th element // to nth element let current = node; let n; for (n = 2; current != null; n++) { // Change result with probability 1/n if (Math.floor(Math.random()*n) == 0) { result = current.data; } // Move to next node current = current.next; } document.write( "Randomly selected key is <br>" + result+"<br>"); } // Driver code head = new Node(5); head.next = new Node(20); head.next.next = new Node(4); head.next.next.next = new Node(3); head.next.next.next.next = new Node(30); printrandom(head); // This code is contributed by rag2127 </script>
Complejidad de tiempo: O (n), ya que estamos usando un bucle para atravesar n veces. Donde n es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Tenga en cuenta que el programa anterior se basa en el resultado de una función aleatoria y puede producir un resultado diferente.
¿Como funciona esto?
Deje que haya un total de N Nodes en la lista. Es más fácil de entender desde el último Node.
La probabilidad de que el último Node sea resultado simplemente 1/N [Para el último o N’ésimo Node, generamos un número aleatorio entre 0 y N-1 y hacemos el último Node como resultado si el número generado es 0 (o cualquier otro número fijo]
La probabilidad de que el penúltimo Node sea el resultado también debe ser 1/N.
The probability that the second last node is result = [Probability that the second last node replaces result] X [Probability that the last node doesn't replace the result] = [1 / (N-1)] * [(N-1)/N] = 1/N
De manera similar, podemos mostrar la probabilidad para el tercer y último Node y otros Nodes. ¡ Consulte el artículo completo sobre Seleccionar un Node aleatorio de una lista de enlaces únicos para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA