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.
Java
// Java program to select a random // node from singly linked list import java.util.*; // Linked List Class class LinkedList { // head of list static Node head; // Node Class static class Node { int data; Node next; // Constructor to create // a new node Node(int d) { data = d; next = null; } } // A reservoir sampling-based function // to print a random node from a // linked list void printrandom(Node 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 int result = node.data; // Iterate from the (k+1)th element // to nth element Node current = node; int n; for (n = 2; current != null; n++) { // change result with // probability 1/n if (Math.random() % n == 0) { result = current.data; } // Move to next node current = current.next; } System.out.println( "Randomly selected key is " + result); } // Driver code public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(5); list.head.next = new Node(20); list.head.next.next = new Node(4); list.head.next.next.next = new Node(3); list.head.next.next.next.next = new Node(30); list.printrandom(head); } } // This code is contributed by Mayank Jaiswal
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